큰 수 만들기 / Greedy

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

 

number의 길이가 아주 큰 값이기 때문에, Greedy로 다음 수가 더 크다면 현재의 수를 지워나가는 방식으로 문제를 해결해야 했다.

✅ Greedy 풀이

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) 
{
    string answer = number;
    auto it = answer.begin();

    while (k > 0)
    {
        if (it + 1 == answer.end() || *it < *(it + 1))
        {
            answer.erase(it);
            it = answer.begin();

            k--;
            continue;
        }

        it++;
    }

    return answer;
}

while문의 if 조건문을 살펴보면, 우선 현재의 it이 가리키는 수보다 다음 인덱스의 수가 더 크다면 현재의 수를 지운다.
그리고 it을 다시 시작점으로 설정하고, 처음부터 다시 검사를 시작해나간다. 이때 현재의 수를 지웠으므로 k 값을 -1 해준다.

"it + 1 == answer.end( )" 조건은 만약 지워야할 글자 수인 k가 남아있는데도 불구하고 it의 다음이 end라면 현재 it을 무조건 지워줘야 end 이상을 가리키지 않는다.

현재의 숫자보다 뒤의 숫자가 크다면, 현재의 숫자를 제거하면 미래엔 가장 큰 수를 얻게 될 것이라는 Greedy 알고리즘을 적용한 풀이이다.