[프로그래머스 Level 2] 큰 수 만들기

🖊️ 문제

큰 수 만들기  

 

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

 

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

🖥️ 코드

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k)
{
    string answer = "";
    int begin = 0, end = k;

    for (int i = 0; i < number.size() - k; i++)
    {
        char c = '0';
        for (int j = begin; j <= end; j++)
        {
            if (number[j] > c)
            {
                c = number[j];
                begin = j;
            }
        }
        answer += c;
        begin++, end++;
    }

    return answer;
}

 

🤔 나의 생각

규칙을 찾다가 머리털 다 뽑힐 뻔했다... 문제를 풀기 위해 노력했던 분들 모두 다 대단합니다. 👏

 

일단 가장 쉽게 알 수 있는 정보는 입력의 길이가 x이고 k가 y일 때 정답의 길이는 x-y이다.

이 다음 반복문을 돌며 문자의 조합을 구해야 하나 싶었는데 입력이 1,000,000자리 이하의 숫자인 걸 보고 체념했다.

 

구글 교수님의 도움을 받을까 하다가... 입출력을 계속 보니 입력의 뒷자리와 정답의 뒷자리가 일부 동일한 것을 알게 되었다. 

직접 써보며 규칙 비스름한 걸 찾게 되었는데 입출력 예시 2번을 보며 정리하는 게 편할 것 같다.

 

입출력 예시 2의 정답의 길이는 4로 number에서 숫자를 제거하며  _ _ _ _ 네 개의 칸에 가장 큰 값을 채워야 한다. 

첫 빈칸 _를 채우기 위해 1231234에서 분홍색으로 칠해진 곳의 최댓값을 찾아야 한다.

 

왜일까? 잘 생각해 보면 빈칸 _에 올 수 있는 숫자들은 1231뿐이다. 만약 12312에서 최댓값을 찾는다면 나머지 34로 남은 빈칸 세 개를 채울 수 없다. 반대로 1231보다 적은 123으로 빈칸을 채울 경우 숫자를 만들 순 있지만 최댓값을 만들 순 없다.

 

즉 내가 구하려는 빈칸을 제외한 남은 빈칸의 개수만큼 number에도 남겨놓고 최대값을 구해야 한다.