[Programmers]탐욕법 > 큰수만들기

1. 앞자리수부터 오른쪽 수보다 왼쪽수가 더 작으면 지운다.

2. 1번을 다 실행했음에도 지워진 수가 없으면(기존 n_size와 number.size가 같다면) number중에서 제일작은 수부터 하나씩 제거한다.

 

---

main포함 코드(c++)

#include <string>
#include <vector>

using namespace std;

string solution(string number, int k) {
    
    int n_size = number.size();
    for(int i=0;i<number.size();i++){
        if( n_size == number.size()+k) break;
        if(number[i] < number[i+1]) { number.erase(number.begin()+i); i=-1; }
    }
    
    if(n_size == number.size()){
        for(int i=0;i<number.size();i++){
            if( n_size == number.size()+k) break;
            number.erase(min_element(number.begin(), number.end()));
            i=-1;
        }
    }
    
    return number;
}


int main() {

    string number = "99991";
    int k = 3;
    solution(number, k);
}

 

 

---

사용한 테스트케이스

"7777" , 1 / 777

"99991", 3 / 99