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

문제

풀이전략

1. 이 문제에서 가장 중요한 것은 첫째자리에 가장 큰 수가 나와야한다.
2. K개의 숫자를 제거하기 때문에, 전체 수의 자릿수를N이라고 하면, N-K개의 숫자들 중 가장 큰 값을 찾아야 한다. 따라서 그 수를 남기고 이후부터는 남아있는 수 - 제거할 수 만큼의 숫자들을 탐색하고 이중 가장 큰값을 찾는것을 반복해야한다.

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string solution(string number, int k) {
    string answer = "";
    int maxNum = -1;
    int maxNumIndex = 0;
    int len = number.length();
    // 제거해야 할 수를 탐색할 수 있는 범위이다. 
    int remain = len - k;
    for(int i=0; i<number.length(); i++){
        if(remain == 0) break;
        // 탐색할 수 있는 범위중 가장 큰 수를 찾는다. 
        for(int j=0; i+j<len; j++){
            if(len - (i+j) < remain ) break;
            
            int num = number[i+j] - '0';
            // 가장 큰 수를 찾으면 그 숫자와 index를 저장한다.
            if(num > maxNum){
                maxNum = num;
                maxNumIndex = i+j;
            }
        }
        // 가장 큰수의 index를 answer에 저장하고 이를 반복한다.
        answer += number[maxNumIndex];
        // 한 수를 찾았으므로 남은 수 또한 1 작게 해준다. 
        remain--;
        maxNum = -1;
        // 가장 큰 수를 기준으로 다시 탐색을 시작한다. 
        i = maxNumIndex;
    }
    
    return answer;
}

소감

이번 문제도 일단 나의 코드만 이해가 되었다. 풀이가 조금 더럽지만 결국엔 K개를 제거할 수 있다면 N-K개를 남길 수 있다는 뜻이니 그만큼 찾고 문제를 해결하는 것이다.