[Level 2] 큰 수 만들기

https://programmers.co.kr/learn/courses/30/lessons/42883

 

숫자로 이루어진 문자열과 k가 주어진다. 해당 문자열에서 k개의 숫자를 제외하고 만들 수 있는 가장 큰 수를 반환하는 것이 문제이다. 숫자의 순서는 바뀌면 안된다. 예를 들어 4912에서 가장 작은 수 2개를 제외 후 9와 4로 94라는 수를 조합하는 게 아니라, 순서는 유지하되 가장 큰 수의 배열인 92를 만드는 것이다.

따라서 맨 앞자리부터 값을 채운다고 할 경우, 특정 범위에서 가장 큰 값을 골라 현재 채워야 할 자리에 넣어주면 된다. 채워야 할 문자열의 길이는 (number.size - k) 이다.

예제 2의 경우 1231234에서 3자리를 제외한 4자리를 채우면 된다. 그러면 다음과 같이 빈칸을 4개 두고 맨 앞자리부터 차례대로 채운다고 생각하면 이해하기 쉽다. 

_ _ _ _ 

그런데 단순히 모든 범위에서 가장 큰 값을 찾으면 안된다. 예를 들어 1231234에서 가장 큰 값은 4인데, 이걸 첫 번째 빈칸에 채우면 나머지 3칸을 채울 수 없게 된다. (순서를 유지해야 하므로)

따라서 현재 채우려는 빈칸을 제외한 나머지 칸의 수만큼 문자열에서 남겨두어야 한다. 예를 들어 1231234에서 첫 빈칸을 채우기 위해 가장 큰 수를 탐색하려면 [0, 3] 범위에서 탐색을 해야 234라는 3칸이 남고, 나머지 세 빈칸을 여기서 찾을 수 있다.

이해하기 쉽게 직접 작성해보면 다음과 같다.

1. "1231234"의 [0, 3] 범위에서 가장 큰 수를 찾는다. -> 3(이를 첫 번째 빈칸으로 채운다)

2. "1231234"의 [3, 4] 범위에서 가장 큰 수를 찾는다. -> 2(이를 두 번째 빈칸으로 채운다)

3. "1231234"의 [5, 5] 범위에서 가장 큰 수를 찾는다. -> 3(이를 세 번째 빈칸으로 채운다)

4. "1231234"의 [6, 6] 범위에서 가장 큰 수를 찾는다. -> 4(이를 네 번째 빈칸으로 채운다)

그래서 순서대로 채운 3234가 정답이다.

우선 채워야 할 남은 빈칸 수를 저장해야 한다. 

1번 단계에선 맨 처음 [0]부터 [7-4](주어진 문자열의 길이 - 남은 빈칸 수)까지의 범위를 탐색한다. 그러면 인덱스 [2]의 3이 최대값이 된다. 그 다음 빈칸을 채우려면 이 최댓값 다음부터 찾아야 하므로 인덱스 [3]부터 [7-3] 까지의 범위를 확인하면 된다.

이렇게 채워야 할 빈칸 수가 0이 될 때까지 반복하면 된다.

코드는 다음과 같다.

 

string solution(string number, int k) {
    
    int ansLen = number.size() - k; 
    string ans(ansLen, ' ');
    int leftLengthToFill = ansLen;

    int beg = 0;
    int end = number.size() - leftLengthToFill;
    while(leftLengthToFill != 0)
    {
        // 현재 자리에 채울 값을 구한다
        int max = -1;
        int maxIdx = -1;
        for(int i = beg; i <= end; ++i)
        {
            int curNum = number[i] - '0'; // char to int
            if(curNum > max)
            {
                max = curNum;
                maxIdx = i;
            }
        }
        
        // 한 자리를 채운다.
        ans[ans.size() - leftLengthToFill] = max + '0'; // int to char
        --leftLengthToFill;
        
        // 다음에 탐색할 범위를 정한다
        beg = maxIdx + 1;
        end = number.size() - leftLengthToFill;
    }
    
    return ans;
}