[탐욕법] 큰 수 만들기

|| 문제설명 ||

1. 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 한다.
2. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있다. 이 중 가장 큰 숫자는 94 이다.
3. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 작성하라.

• number : 문자열 형식의 숫자
• k : 제거할 수의 개수

_ number : 1자리 이상, 1,000,000자리 이하, 숫자
_ k : 1 이상 number의 자릿수 미만인 자연수

---

|| 문제해결방법 ||

1. 한 번에 풀기: O(n)

지운 숫자 개수 : cnt = 0

맨 앞자리부터 k번째 까지 가장 큰 값을 구한 뒤 그 수 보다 작은 것들은 제거, cnt++

k번째 이후부터는 해당 자리가 다음 자리보다 작으면 제거, cnt++

cnt == k가 되면 그 숫자를 answer에 저장하고 return

2. 여러가지 중에 가장 큰 값 구하기

---

|| 코드 ||

[2020.09.03] 실패

- 제거ver.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(int a, int b) {
    return a > b;
}

string solution(string number, int k) {
    string answer = "";
    string tmp(number.begin(), number.begin() + k + 1);
    
    sort(tmp.begin(), tmp.end(), compare);
    
    for(int i=0; i<number.size(); i++) {
        if(i < k && number[i] < tmp[0]) {
            number.erase(number.begin() + i);
            i--; k--;
        }
        else {
            if(number[i] < number[i+1]) {
                number.erase(number.begin() + i);
                i--; k--;
            }
        }
        if(!k) break;
    }
    return number;
}

- 삽입ver.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(int a, int b) {
    return a > b;
}

string solution(string number, int k) {
    int cnt = 0, i;
    string answer = "";
    string tmp(number.begin(), number.begin() + k +1);
    
    sort(tmp.begin(), tmp.end(), compare);
    
    for(i=0; i<number.size(); i++) {
        if(number.size() - i - 1 )
        if(i <= k && number[i] == tmp[0]) {
            answer.push_back(number[i]);
        }
        else if(i > k && number[i] >= number[i+1]) {
            answer.push_back(number[i]);
        }
        else {
            cnt++;
            if(cnt == k) {
                string t(number.begin() + i + 1, number.end()+cnt-k);
                answer.append(t);
                break;
            }
        }
    }
    return answer;
}

• 특수상황

1) 같은 숫자들만 있을 경우

→ number = "77777777777", k = 4 | return "77777777777" | ans "7777777"

→ number = "1200397909", k = 9 | return "999" | ans "9"

→ number = "17779999", k = 3 | return "779999" | ans "79999"

같은 숫자만 있을 때 + 같은 숫자가 반복되는게 여러 개일 때 앞에가 더 작은 숫자이면 어떻게 숫자를 빼고 return 할 것 인가

---

[2020.09.06] 성공

- 갈아엎기

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    int t = 0;
    string answer = "";
    k = number.size() - k;
    for(int i=0; i < number.size(); i = t+1) {
        char max = '0';
        for(int j = i; j <= number.size()-k; j++) {
            if(max < number[j]) {
                max = number[j];
                t = j;
            }
            if(number[j]=='9') break;
        }
        answer += max;
        k--;
        if(!k) break;
    }
    return answer;
}