프로그래머스 - 큰 수 만들기(C++)

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/42883

문제 난이도

Lv 2

문제 접근법

number 자리수가 백만이기 때문에, dfs를 돌리면 시간초과가 난다.
그러므로 삭제한다는 수가 k면 출력해야하는 수는 number.size() - k이다.
그럼 저 수만큼 출력이 가능하려면 먼저 맨 앞에서부터 삭제하려는 수 중에서 큰 수를 찾는다. 그 수를 빼고 삭제한다면? 앞에 있는 수는 저절로 큰수.
그리고 그 수 +1 기준으로 뒤에 K 만큼 살펴보고 그 중에 큰 수를 뽑아 나머지는 다 삭제한다.
K만큼 삭제했으면 그 뒤에 있는 수들은 그대로 붙여주면 된다.

통과 코드

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

using namespace std;


string solution(string number, int k) {
	string answer = "";
    int idx = -1;
    for(int i=0; i<number.size()-k; i++){
        char maxV = ' ';
        for(int j=idx+1; j<=k+i; j++){
            if(maxV < number[j]){
                maxV = number[j];
                idx = j;
            }
        }
        answer += maxV;
    }
	return answer;
}

피드백

시간초과를 어떻게하면 줄일까 고민을 많이 했던 문제였다. 그리디 라는 걸 알아서 어떻게 단순하게 접근할까를 했지만 결국은 틀려서 다른 코드를 참고했다. size-k 까지는 알고 있기에 그 뒤에 접근법이 궁금했는데 저런식으로 할 수 있다는게 의외였다.
그치만 틀린 건 사실이기에 보고 나서 완전 허탈 + 난왜이렇게 생각하지 못했지? 가 들었다 어떻게하면 저렇게 접근할까!