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

📄 문제

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

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

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

 

📝 풀이

number "12345", k 2일때

i 반복문은 0부터 2까지 반복합니다. (number.size() - 2)

 

i가 0일때에는 startIdx가 0이므로, j는 0부터 시작합니다. j는 2까지 반복할 수 있습니다.

그러면, {1, 2, 3}에서 가장 큰 값은 3이고, maxIdx는 2가 됩니다.

 

i가 1이 되면, startIdx는 3이 됩니다. j는 3부터 시작합니다. j는 3까지 반복할 수 있습니다. (j <= k + i)

이 상태에서는 최대값이 3이 됩니다. maxIdx는 3이 됩니다.

 

i가 2가 되면, startIdx는 4가 됩니다. j는 4부터 시작하며, 4까지 반복할 수 있습니다.

 

#include <string>
#include <vector>
 
using namespace std;
 
string solution(string number, int k) {
    string answer = "";
 
    int startIdx = 0;
    // number에서 k개를 뺀 것을 뽑기 위해 number.size() - k 만큼 반복
    for(int i = 0; i < number.size() - k; ++i)
    {
        char maxChar = number[startIdx];
        int maxIdx = startIdx;

        // 시작 위치로부터 k + 1번까지 반복 (뒤에서 뽑을 것을 보장하기 위해 반복을 제한)
        // 만약, 현재 뽑은 값이 마지막 인덱스가 가장 크다면, 다음에 뽑는 경우는 호출되지 않을 수 있음
        // 12345 중 k가 2인경우, {1, 2, [3]}, [4], [5] 가 뽑힘
        for(int j = startIdx; j <= k + i; ++j)
        {
            // 현재 선택에서 최상의 값을 구하기
            if(maxChar < number[j])
            {
                maxChar = number[j];
                maxIdx = j;
            }
        }
        
        // 정답에 추가하고, 다음 반복문은 maxIdx + 1번부터 뽑기 시작
        answer.push_back(maxChar);
        startIdx = maxIdx + 1;
    }
 
    return answer;
}

• number에서 k개를 뺀 수를 구하는 문제이기에 number.size() - k 만큼 반복을 해 해당 반복문에서 수를 무조건 1개씩 뽑아 정답에 삽입하도록 합니다.
• j가 startIdx로부터 k + 1까지만 뽑아야 합니다. 그 이유는, 다음 뽑기에서 영역에 제한을 두어 나중에 값을 무조건 뽑을 수 있도록 보장하기 위해서입니다.
• 이런 상태에서, startIdx부터 k + i까지 값 중 가장 큰 값을 뽑아 정답에 삽입합니다.