프로그래머스 - 큰 수 만들기

프로그래머스 - 큰 수 만들기

문제를 보고 어떻게 풀지 감이 잘 안와서 일단 조합을 만드는 것으로 시도했다.
문제는 제한 조건에서 number가 1,000,000자리 이하인 숫자인데, 풀면서도 이건 시간 때문에 안되겠구나 생각을 했고,
실제 결과도 시간초과로 실패햇다.

#include <string>
#include <vector>

using namespace std;

int result[1000001];
int visit[1000001];

string answer = "";
void combination(const string number, int n, int r, int depth)
{
    if(r == depth) {
        string ans = "";
        int cnt = 0;
        for(int i=0; i<n; i++) {
            if(i == result[cnt]) 
                cnt++;
            else 
                ans.push_back(number[i]);
        }
        
        if(answer.compare(ans) < 0) 
            answer = ans;
        
        return;
    }
    
    int start = depth == 0 ? 0 : result[depth - 1];
    for(int i=start;i<n;i++) {
        if(visit[i] == 0) {
            visit[i] = 1;
            result[depth] = i;
            combination(number, n, r, depth + 1);
            visit[i] = 0;
        }
    }   
}

string solution(string number, int k) {
    int size = number.size();
    combination(number, size, k, 0);
    return answer;
}

O(n)만에 무조건 풀어야할 것 같아서 고민을 좀 하고 공부를 좀 했다...

string solution(string number, int k) {
    int size = number.size();
    string answer = "";
    
    for(int i=0;i<size;i++) {
        if(answer.empty()) {
            answer.push_back(number[i]);
            continue;
        }
        if(k > 0) {
            int start = answer.size() - 1;
            for(int j=start; j>=0; j--) {
                if(k == 0)
                    break;
                if(answer[j] < number[i]) {
                    k--;
                    answer.pop_back();
                    continue;
                }
                break;
            }
        }
        answer.push_back(number[i]);
    }
    // 예외 처리
    if(k != 0) {
        while(1) {
            if(k == 0)
                break;
            k--;
            answer.pop_back();
        }
    }
    return answer;
}

얻은 결과는 위 코드와 같다.

큰 흐름은 일단 앞에서부터 쭉 가면서 비교를 하면서 가장 큰 앞자리 숫자를 만들어주는 것이다.

예를 들어서 설명하자면,

"1924"의 경우

1의 경우.

• answer가 비어있기 때문에 바로 push_back해준다.
  - 현재 answer : [ 1 ]
  9의 경우.
• answer에서 가장 뒷 부분부터 비교를 하면서 9보다 작은 숫자가 있는 경우 pop_back 해준다.
• 또한 pop_back이 발생할 때마다 k 값을 줄여준다. 즉, 결과 값에서 제외되는 숫자이다.
  - 현재 answer : [ 9 ]
  2의 경우.
• 2와 answer에서 가장 뒷 부분인 9를 비교해서, 9가 더 크므로 그냥 2를 push_back해준다. (answer 값들이 비교 대상)
  - 현재 answer : [ 9 2 ]
  4의 경우.
• 4와 answer의 뒷부분인 2부터 비교를 시작. 2의 경우 4보다 작으므로 pop_back 후 k--
• 9의 경우 4보다 크기 때문에 4를 push_back 해준다.
  • 현재 answer : [ 9 4 ]

다른 예제도 위와 같이 해주면 되는데,
number : 999 // k : 1 같은 경우 "99"가 답으로 나와야하는데 "999"로 나온다.

이를 위해서 따로 예외처리를 해줘야한다. (테스트 케이스 12번이 그러한 케이스인듯)

결과는 위와 같다.