[프로그래머스 lv2] 큰 수 만들기 (c++)

문제

---

 

 

풀이

---

 

문제는 이해하기 쉽지만, 아이디어를 떠올리는 것이 굉장히 어려웠다. 

 

number 최대 길이는 1000000이기에 조합을 위해 dfs를 쓰거나 하면 시간 초과가 날 것이다.

 

그리디(greedy)한 , 즉 매 순간 최선의 결과를 반환하는 걸 고르는 방법을 통해 문제를 풀어야한다.

 

 

한 번 예제를 따라가면서 방법을 찾아보도록 하자.

 

 

 

위 그림은 0이 10개 있는게 아니라, 무작위 숫자가 10개 있는 걸 나타낸 그림이다. k는 4로 주어진 상태이다. 

 

이 상태라면 우리는 10개의 숫자 중 총 4개의 숫자를 제거해서 최대의 숫자를 만들어야한다. 

 

최대의 숫자는 당연하게도 자리수가 크거나, 앞자리 숫자가 제일 큰 숫자일 것이다. 여기서 자리수는 고정되니, 앞자리 숫자가 최대한 크도록 숫자를 골라야 할 것이다.

 

문제에서 중요한 아이디어는 바로 number를 기준으로 반복문을 돌리는 게 아니라, 정답의 길이 만큼 문자열을 돌리는 것이다. 

 

 

위에 예시에서는 총 6번 반복문을 돌려 정답을 하나씩 찾아 answer에 붙이는 것이다.

 

 

 

 

그렇다면, 어떤 과정으로 진행되는가?

 

 

 

1. 첫 번째 순환.

 

 

 

처음에 이렇게 앞의 5개의 숫자 중 최댓값을 찾는다. 이유는 만약 저거보다 많은 숫자들 안에서 최댓값을 찾으면, 이후 나머지 남는 숫자 개수는 5개 미만이 된다.

 

만약 저거보다 적은 숫자들 안에서 최댓값을 찾으면, 그 숫자가 앞에 올 최대 숫자가 된다는 보장을 할 수 없다. (뒷자리에 6개 숫자보다 많이 남아있는데, 만약 그 중 더 큰 수가 있으면 최댓값이 되지 않을 것이다. )

 

우리가 찾아야하는 숫자의 자리수는 6자리다!! 이 사실을 꼭 알아야한다. 

 

 

만약 범위를 노란 원으로 넓혀서 최댓값을 찾으면, 이후 나머지 숫자로는 6자리를 못 만들 수도 있는 상황이 올 수 있다. 극단적으로, 노란색 원 안에 숫자 중 맨 오른쪽 숫자가 가장 큰 수라고 해보자. 

 

그 숫자를 선택하고 그 다음 시작할 때는 오른쪽에는 숫자가 3개밖에 남지 않아, 결국 6자리를 만들 수 가 없다.

 

 

 

즉, 오른쪽에는 항상 선택해야할 숫자 개수는 남아있어야 한다.

 

 

 

 

2. 첫 번째 범위에서 선택한 후, 그 다음은 그 선택했던 숫자 뒤에서 부터 반복문을 시작해야한다.

 

 

 

만약 첫 번째 범위에서 3번 째 숫자가 최댓값이라면, 그 다음 반복문은 4번 째 자리 부터 시작해야한다.

 

당연하게도, 숫자 순서는 정해져 있기 때문에 그렇다.

 

 

몇 번 반복해야하는가? 바로 뒤에 남는 숫자가 이번에는 4자리 남는 범위까지 반복하는 것이다. 

 

이유는 1번에 나온 원리와 같다. 단지 앞에서 숫자 하나를 뽑았기에, 이제 6개가 아닌 5개의 숫자를 뽑아야 하는 상황이라 1 줄어든 것이다. 그렇다면 그 다음은? 뒤의 숫자가 3자리 남는 만큼 돌리면 된다. 그 다음도 계속 1 씩 줄어드는 것이다.

 

 

 

이걸 코드로 표현해보자.

 

 

#include <bits/stdc++.h>

using namespace std;

string solution(string number, int k) {
    string answer = "";
    int start_idx = 0;

    
    for(int i = 0 ; i < number.size() - k ;i++){
        
        int Max = -1;
        int tmp = start_idx;
        for(int j = start_idx; j <= k + i ; j++ ){
            if(Max < number[j]){
                Max = number[j];
                tmp = j;
            }
        }
        
        start_idx = tmp + 1;
        answer += Max;
    }
    return answer;
}

 

 

start_idx는 반복문이 시작하는 인덱스 위치를 나타낸다. 위의 그림에서는 최댓값 숫자를 선택한 후, 그 다음 자리가 되겠다.

 

가장 중요한 부분은 두 번째 반복문이다. j <= k + i로 설정하는 것이다. 이렇게 하면 숫자 하나를 선택할 때 마다 그 다음 반복문의 범위가 1씩 증가하게 된다.

 

 

 

이번 문제를 보면서, 문제를 보고 반복문을 설계할 때 꼭 주어지는 배열 전체를 반복문을 통해 접근하려는 생각으로 자주 접근하던 습관을 다시 돌아보게 되었다. 주어지는 배열 사이즈만큼 도는게 아니라, 정답의 길이만큼 반복문을 돌려볼 생각도 해야할 것이다.