[PG/C++] 프로그래머스 Lv2 - 큰 수 만들기

😊문제 설명

해결 방법이 쉽사리 떠오르지 않는 구현 문제였다.

문자열 형태로 주어진 숫자 입력 중 K개를 제거하여 만든 문자열이 최대가 되도록 한다.

🐹 코드 설명

먼저, 큰 숫자를 만들기 위해서는 앞쪽의 숫자들 중 제거할 수 있는 것을 최대한 제거하여 제일 앞의 숫자를 큰 숫자로 만들어야 한다. 이때 제거할 수 있는 갯수는 정해져있으므로, 이 숫자를 제거할 지 말 지 앞으로 더 제거할 수 있는 갯수(K)를 기반으로 결정하면 된다.

4177252841라는 예제입력으로 설명해보겠다.

• 4 입장에서, 자신을 없애지 않으면 뒤의 네 가지 숫자를 없앨 수 있다. (K = 4) 뒤의 네 가지 숫자는 1, 7, 7, 2이다. 이 중에서 7은 4보다 크며, 7을 제거하는 것보다 4를 제거하는 것이 더 좋은 선택이다. 따라서 4를 제거한다.
• 이제 K = 3이다. 1 입장에서도 마찬가지로 자신을 없애지 않으면 뒤의 세 가지 숫자인 7, 7, 2를 없앨 수 있다. 7를 제거하는 것보다 3을 제거하는 것이 더 좋은 선택이므로, 3을 제거한다.
• K = 2이고, 7은 그 뒤의 두 숫자인 7, 2보다 크거나 같으므로 제거하지 않고 넘어간다. 그 이후의 7도 마찬가지이다.
• 2 입장에서, 5, 2와 자신을 비교해보면 5가 자신보다 더 크다. 따라서 제거한다.
• K = 1이고, 5는 2보다 크므로 제거하지 않고 넘어간다. 2가 8과 비교되어 제거된다.

이러한 과정을 거쳐 제거되지 않은 숫자들이 최종적으로 리턴된다.

이때, 1111 혹은 4321이라는 예제입력처럼 같거나 큰 숫자들이 연속으로 나오는 경우에는 K가 줄어들지 않고 계속 answer에 추가된다. 따라서 모든 숫자의 순회를 마쳤음에도 K가 0이 아니라면, 제일 뒤의 숫자를 제거하는 것이 제일 좋다. 왜냐하면 숫자는 이미 큰 것이 앞쪽에 위치해있기 때문이다.

👩‍💻 소스 코드

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

using namespace std;

string solution(string number, int k) {
    string answer = ""; 
    for(int i = 0; i < number.length(); i++){
        bool flag = true; // 현재 숫자를 선택해도 되는지 ? 
        for(int j = 1; j <= k; j++)
            if(number[i]  < number[i + j]) {
                flag = false; 
                k--; 
                break;
            }
        if(flag)
            answer.push_back(number[i]);
    }
    while(k != 0){
        answer.pop_back();
        k--; 
    }
    return answer;
}