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

문제 설명

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

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

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

제한사항

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

---

풀이

주어진 숫자로 만드는 가장 큰 수는 가능한한 앞에서부터 내림차순의 형태를 가져야한다. 그래서 해당 논리를 코드로 구성하고 제출했는데, 마지막 테스트케이스를 통과하지 못 했다. 다시 고민해보니, 오름차순으로 구성된 뒤에 지워야할 수의 개수가 남는 경우를 처리하지 않았다. 따라서 그 경우에는 뒤에서부터 숫자를 삭제하도록 했다.
같은 레벨의 문제더라도 그리디 문제가 유독 시간이 오래걸리는 느낌이다. 정확히 기록하기 위해서 문제를 푼 소요 시간까지 써놔야겠다.

실패 코드

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    int cnt = 0;
    for(int i = 1; i < number.length(); ++i){
        while(i > 0 && number[i-1] < number[i]){
            number.erase(number.begin() + i - 1);
            --i;
            ++cnt;
            if(cnt == k) break;
        }
        if(cnt == k) break;
    }
    return number;
}

통과 코드

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    int cnt = 0;
    for(int i = 1; i < number.length(); ++i){
        while(i > 0 && number[i-1] < number[i]){
            number.erase(number.begin() + i - 1);
            --i;
            ++cnt;
            if(cnt == k) break;
        }
        if(cnt == k) break;
    }
    for(int i = number.length() - 1; i >= 0; ++i){
        if(cnt == k) break;
        number.erase(number.begin() + i);
        ++cnt;
    }
    return number;
}