큰 수 만들기 42883

문제

접근 방법

꽤 오랜 시간 생각했던 것 같다. 처음에는 오른쪽에서 시작하여 큰 수를 포함하는 식으로 생각했다. 우선순위 큐를 활용하여 현시점 가장 큰 수와 일치하면 기록해주고 앞으로의 기회가 남았을 때만 (큰 수의 오른쪽을 다 하고도 남을 정도면) 큰 수의 왼쪽으로 가게끔 말이다. number가 1,000,000자리 숫자이기도 하고 코드를 잘못 짠 것 같아서 갈아엎었다.
작은 수를 지워주는 방식을 생각했다. 큰수의 오른쪽보단 왼쪽에 있는 값들을 지워야 한다. (2314에서 1을 지우는 것보단 2를 지우는 것이 더 큰 수를 보장한다.)
왼쪽에서 접근해서 바로 오른쪽보다 작은 수일 시 지워주는 방식으로 하였다.

코드

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k)
{
    for (int i = 0; number[i + 1]; ++i)
    {
        if (k == 0)
            break;
        if (number[i] < number[i + 1])
        {
            number.erase(i, 1);
            i = -1;
            k--;
        }
    }
    number.erase(number.length() - k, k);
    return number;
}

풀이

앞에서부터 비교하며 오른쪽보다 작으면 지워주고 0부터 시작한다.

number.erase(number.length() - k, k);

98765432111... 같은 숫자가 나타난다면 오른쪽값이 작기에 끝까지 갈 것이다.
뒷값은 작은 숫자라는 것이 확실하기에 뒤에서부터 잘라주었다.

처음 접근했던 방식보다 간단해서 허탈했다.
그리디는 생각을 간단하게 하는 것이 중요한 것 같다.