큰 수 만들기 Programmers 프로그래머스 C++

문제 설명

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

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

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

제한 조건

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

입출력 예

number	k	return
"1924"	2	"94"
"1231234"	3	"3234"
"4177252841"	4	"775841"

구현

앞서 탐욕법에 대하여 정리해놓은 것처럼 탐욕법은 현재 볼 수 있는 대상 중에서 조건에 만족하는 가장 좋은 경우의 수를 찾는 문제이다.

해당 문제에 대한 해결법은 다음과 같다. 첫 번째 예에서 우리는 1924에서 2개의 수를 뽑아야 한다. 문제 설명에서 주어진 예시처럼 조합을 통하여 모든 경우의 수를 만들어내고 그중에서 가장 큰 수를 뽑아낼 수도 있다.

하지만 그런 식으로 문제를 푼다면 우리는 1924의 순서가 변하지 않는 상황에서 2개의 수로 만들 수 있는 가장 큰 수를 뽑아내야 하는데 그것을 코딩으로 옮기기가 과연 쉬울까? 하는 생각을 해보아야 한다.

그렇다면 접근 방법을 바꾸어 가장 앞에서부터 수를 보는 것이다.

1924에서 2개를 골라서 가장 큰 수를 뽑는 방법은 다음과 같다. (뽑아낼 개수 j = n-k)

1. j = 2이고 2 자릿수를 만들어야 하므로 처음 뽑는 수는 1, 9, 2 만 볼 수 있다. 따라서 1, 9, 2중에서 가장 큰 수를 골라서 제일 앞에 넣는다. 1개를 골랐으므로 j = 1 이 된다.
2. j = 1이고 2자리 수중 앞의 자리를 제외하고 1개의 수를 뽑아야 한다. 이 상황에서 뽑을 수 있는 수는 1, 9를 제외한 2, 4 중에서 가장 큰 수이다.
3. 따라서 처음 뽑은 수는 9이고 두 번째 뽑은 수는 4 여야 한다.

즉 n개의 자리를 가진 수 중에서 k개를 골라서 가장 큰 수를 뽑는 방법은 다음과 같다.

1. start : 0부터 end : n-j까지의 인덱스를 탐색하며 가장 큰 수(index)를 골라내서 제일 앞에 붙인다.
2. start : index + 1부터 end : n-j까지의 인덱스를 탐색하며 가장 큰 수(index)를 골라내서 그다음 붙인다.
3. 2번의 과정을 j가 0이 될 때까지 반복한다.

코드로 옮기면 다음과 같다.

---

전체 코드는 아래에서 볼 수 있다.

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

using namespace std;

string solution(string number, int k)
{
    string answer = "";
    int ans_size = number.size() - k;
    while (ans_size != 0)
    {
        int max = 0;
        int idx = 0;
        for (int j = 0; j <= number.size() - ans_size; j++)
        {
            if (number[j] - '0' > max)
            {
                max = number[j] - '0';
                idx = j;
            }
        }
        answer.push_back(number[idx]);
        for (int j = 0; j <= idx; j++)
            number.erase(number.begin());
        ans_size--;
    }
    return answer;
}