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

https://programmers.co.kr/learn/courses/30/lessons/42883

코딩테스트 연습 - 큰 수 만들기

풀이 방법

수를 제거해 최대한 큰 숫자를 얻으려면, digit이 큰 수를 최대한 앞쪽에 위치하도록 삭제해야 한다. 따라서 먼저 가장 큰 digit을 찾고,  이 digit을 삭제하지 않을 것을 mark[] 배열에 체크하고 추가한 digit 개수 added를 1 증가시킨다.

char max_digit = number[start];
int max_idx = start;
for(int i=start+1; i<=end; i++){
    if(!mark[i] && number[i] > max_digit){
        max_digit = number[i];
        max_idx = i;
        if(max_digit == '9') break;
    }
}

mark[max_idx] = true;
added++;

 

그 후, 먼저 오른쪽 서브 배열과 왼쪽 서브 배열을 recursive하게 확인한다.

add_char(number, max_idx+1, end, to_add, mark);
add_char(number, start, max_idx-1, to_add, mark);

 

한편, added가 추가해야할 digit 개수와 같아지면 result 문자열에 결과값을 저장한다.

if(added == to_add){
    for(int i=0; i<n; i++){
        if(mark[i]) result += number[i];
    }
    return;
}

 

number의 길이가 N이고, 이 중 K개의 digit을 삭제해야 할 때 평균적인 시간 복잡도는 O((N-K)logN)이다. 최악의 경우, O(N^2)이다.

 

전체 코드는 여기서 확인할 수 있다.

---

다른 사람의 풀이 중, 되게 간단하게 푼 풀이방법이 있었는데 이에 대해 살펴보자. (출처)

 

먼저 number 문자열의 k번째 문자부터 끝까지 answer 문자열에 저장한다. 이는, 일단 자릿수가 큰 k개의 digit을 삭제하는 것으로 가정한다는 의미이다.

string answer = number.substr(k);

 

그 후, number의 (k-1)번째 문자부터 0번째 문자까지 answer의 digit과 바꾸어 더 큰 수를 만들 수 있는지 확인한다. 0번째가 아니라 (k-1)번째 문자부터 살펴보는 이유는 digit을 삭제해도 원래 순서를 그대로 지키면서 삭제해야 하기 때문이다. 따라서 자릿수가 작은 digit부터 차례대로 교체해나가면 순서를 그대로 유지할 수 있다.

for(int i=k-1; i>=0; i--){
    int j=0;
    while(j < len){
        if(number[i] >= answer[j]){
            char tmp = number[i];
            number[i] = answer[j];
            answer[j] = tmp;
            j++;
         }
         else break;
    }
}

 

전체 코드는 여기서 확인할 수 있다.