[C++, 코딩테스트] 프로그래머스 : 큰 수 만들기 with 그리디

문제 링크

 

#include <string>
#include <vector>
#include <iostream>

using namespace std;

string solution(string number, int k) {
    string answer = "";    
    int len = number.size();
    int answerLen = len - k;
    int limit = len - (answerLen - 1);
    int q = 0;
    int nextIdx = 0;
    for (int i = 0; i < answerLen; i++){
        char bigNum = -1;
        q = nextIdx;
        while (q < limit){
            if (max(number[q], bigNum) == number[q] && number[q] != bigNum){
                bigNum = number[q];
                nextIdx = q + 1;
            }
            q++;
        }
        answer += bigNum;
        limit++;
    }
    return answer;
}

 

즉 "1924" 문제에서 k = 2인 경우, 2문자를 제외해서 가장 큰 값을 찾아야할 때, 나올 수 있는 경우의 수는 [19, 12, 14, 92, 94, 24] 이렇다. 처음 아이디어로는 조합을 이용해서 모든 경우의 수를 탐색해야하나? 싶었는데 number의 값이 1,000,000자리까지 늘어날 수 있기 때문에 시간복잡도에서 실패할 수 있을 것 같았다. 

 

이 문제는 앞에서부터 가장 큰 수를 정해주면 가장 큰 값을 만들 수 있다는 아이디어를 사용했다. 즉, 

 

위 그림같은 순서로 큰 수를 정하면 최대값을 구할 수 있다.