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

문제

---

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

풀이

---

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하기 위해 탐욕법을 사용하여 풀이한다. 숫자 제거 후 남은 숫자들의 순서대로 가장 큰 숫자가 정해지므로, 앞자리를 큰 수로 유지하기 위해 k-1 개 이상의 숫자를 뒤에 가지고 있는 가장 큰 숫자를 탐색하고 뒷자리도 이와 같이 반복하여 앞자리를 최대로 할 수 있는 경우의 수를 탐색한다.

#include <string>
#include <vector>
#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 max_num = '0';
        
        for (int j = idx + 1; j <= k + i; j++)
        {
            if (max_num < number[j])
            {
                max_num = number[j];
                idx = j;
            }
        }

        answer += max_num;
    }


    return answer;
}