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

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    int window_size = number.size() - k;

    int max_idx = -1;
    char max_val;
    for(int i=0 ; i< window_size ; i++) {
        max_val = '0';
        for(int j = max_idx + 1 ; j<i+k+1 ; j++) {
            if(max_val < number.at(j)) {
                max_val = number.at(j);
                max_idx = j;
            }
        }
        answer.push_back(max_val);
    }    
    return answer;
}

 

i번째의 수를 고를 때, k 개를 뽑아야 되니까 최소 i부터 k+1 범위에 있는 수중에서 큰 수만을 고르게 되면 결국 전체적으로 봤을 때 최대 값이 생기게 된다.

그리디한 방법 하에, answer 는 앞자리 수가 크면 클수록 가중치가 크기 때문에 앞에서부터 뽑힐 수 있는 모든 후보군 중에서 큰 값을 뽑게 되면 결국 제일 큰 값이 처리되기 때문에 답이 나온다.

 

쉽게 설명하자면 각 자리수의 수를 확인할 수 있는 윈도우를 설정하고, 해당 윈도우에서 가장 큰 값을 체킹하고 answer 에 넣어준다. 그렇게 되면 확실하게 k 개를 뺀 개수가 나오게 되고 가장 큰 값이 답으로 나오게 된다.