[PS] 큰 수 만들기

문제

프로그래머스

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

 

풀이

가장 큰 수를 만들기 위해서는 선택할 수 있는 숫자 중에서 가장 큰 수를 먼저 선택해서 앞자리 수로 만들어야 한다.

따라서 만들어야 하는 숫자 수 만큼 반복해서 범위 안에서 가장 큰 수를 뽑아서 붙인다.

범위를 지정해서 그 안에서 제일 큰 수를 고르면 항상 전체 숫자를 크게 만들 수 있다.

 

슬라이딩 윈도우 기법

슬라이딩 윈도우 기법에 따라,

0번째(i=0)에서 시작한다 가정했을 때 0~K번째(K+i+1개)까지의 범위 내에서 큰 수를 골라야

그 다음번째 범위에서 선택할 수 있는 숫자들이 M-1개가 된다.

* K: 제외할 숫자 개수 M: 만들어야 하는 숫자 개수

 

예시

입력받은 수: 1924, K: 2
4자리 수에서 2개를 제외해야 하므로 만들어야 하는 숫자는 2자리 수이다.

K+i+1개 탐색을 위해 0~K까지 탐색
192 중 가장 큰 수: 9
answer : 9

9의 다음부터 탐색
24 중 가장 큰 수: 4
answer : 94

 

코드

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    
    int num = number.length() - k; // 구해야할 숫자 크기
    int idx = 0;
    
    // num 개의 숫자 고르기
    for(int i = 0; i < num; i++){
        // 제일 큰 수 고르기
        char maxChar = number[idx]; // 제일 처음에 있는 수
        int maxIdx = idx; // 인덱스
        // k개 탐색해서 가장 큰 수 고르기
        for(int j = idx; j <= k+i; j++){
            if(maxChar < number[j]){
                maxChar = number[j];
                maxIdx = j;
            }
        }
        answer += maxChar; // string에 그냥 char + 해서 넣을 수 있음
        idx = maxIdx + 1; // 고른 다음 부분부터 탐색
    }
    
    return answer;
}

 

 

회고

문제 이해하는데 꽤나 애먹었다

연속된 가장 큰 수를 만드는 줄 알고 코딩했다가 뒤늦게 깨달음..