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

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예

Solution

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

string solution(string number, int k) {
    string answer = "";
    for(int i = 0; i < number.length(); i++){
        while(!answer.empty() && answer.back() < number[i] && k > 0){
            answer.pop_back();
            k--;
        }
        if(k == 0){
            answer += number.substr(i, number.length() - i);
            break;
        }
        answer.push_back(number[i]);
    }
    return answer.substr(0, answer.length() - k);
}

Greedy 문제가 나오면 일단 테스트 케이스들을 노트에 적어 볼 필요가 있단 생각이 매우 드는 문제다.
그림을 한번 보자. 좀 못쓰긴 했지만 양해바란다.

마지막 테스트케이스는 4177252841 이라는 숫자에서 4개의 숫자를 빼서 775841 이라는 숫자를 만들어냈다.
정말 죽자고 K개의 데이터를 뺀 조합중에서 큰 것을 구할수도 있겠지만 그렇게 하려다간 데이터 범위가 꽤나 크기때문에 그냥 상식적으로 생각해봐야 한다.
1231234 라는 숫자에서 3개의 데이터를 빼서 3234라는 수를 만드는 경우도 마찬가지다. 그림으로 그려보면 다음과 같다.

일단 데이터를 첫번째 자리부터 보기 시작한다. 큰 수라는 건 큰 자릿수가 클 수록 큰 수라고 생각할 수 있기 때문에 왼쪽 데이터부터 보는 것이다. 끝까지 보면서 만약에 가장 큰 자릿수로 갱신 된 녀석이 다음에 올 수 있는 수보다 작다? 그러면 더 큰 자릿수를 해당 숫자로 만들면 되기 때문에 제거한다. 이 과정을 진행한 횟수를 세어서 K만큼 진행했다면 더이상 숫자를 뺄 수 없기 때문에 나머지 숫자를 모두 더한다가 핵심이다.

그리디 문제를 풀 땐 테스트 케이스를 일단 꼭 분석해보고 알고리즘을 설계해야한다. 일단 무작정 어떤 알고리즘을 도입하자! 이렇게 생각할 수 있는 문제는 아니라 오히려 더 어렵게 느껴지는 것 같다.