[그리디, 난이도 중] 프로그래머즈, 큰 수 만들기

문자열로 주어진 정수에서 k개의 수를 제거해서 만들 수 있는 가장 큰 수를 계산하는 문제이다.

백준에서 이런 유형의 문제를 풀었던 기억이 있었던 덕에 금방 해결할 수 있었다.

 

본인의 접근법은 스택의 원리를 이용하는 것이다.

순서대로 정수를 벡터에 넣으며, 기존 벡터의 마지막 인덱스 값(스택 상에선 top)이 현재 push한 정수보다 작을 경우 이 마지막 인덱스 값을 제거해주는 과정을 반복한다. 제거할 때마다 k의 카운트는 1씩 감소시켜야 한다.

 

해당 규칙으로 입력값의 정수들을 모두 벡터에 넣었음에도 불구하고 수를 k만큼 제거하지 못했을 경우도 있다.

이 과정까지 잘 수행 했다면 벡터의 요소는 ex) (5,4,3,2,1), (7,5,3,2,1), (9,9,7,7,5,5) 같이 내리막수일 것인데, 남은 k가 1 이상일 경우를 말하는 것이다.

 

이 때는 벡터의 마지막 인덱스 값을 제거해주는 과정을 남은 k만큼 반복해주면 최종적으로 문제의 조건에 맞는 가장 큰 수를 얻을 수 있다.

 

예시 설명)

"4177252841", k=4 -> (답) "775841

4 -> push [현재 벡터 요소 (4)], k=4

1 -> push [현재 벡터 요소 (4,1)], k=4

7 -> 1제거 -> 4제거 -> push [현재 벡터 요소 (7)], k=2

7 -> push [현재 벡터 요소 (7,7)], k=2

2 -> push [현재 벡터 요소 (7,7,2)], k=2

5 -> 2제거 -> push [현재 벡터 요소 (7,7,5)], k=1

2 -> push [현재 벡터 요소 (7,7,5,2)], k=1

8 -> 2제거 -> k=0이 되므로 반복문은 더 이상 수행되지 않음 [현재 벡터 요소 (7,7,5,8)], k=0

4 -> push [현재 벡터 요소 (7,7,5,8,4)]

1 -> push [현재 벡터 요소 (7,7,5,8,4,1)]

 

테스트 케이스 12개 모두 통과

#include <string>
#include <vector>
using namespace std;

string solution(string number, int k) {
    vector<int> v;
    string answer = "";
    int num,sd;
    for(int i=0;i<number.length();i++){
        num = number[i]-'0';
        v.push_back(num);
        sd=v.size();
        while(k!=0 && sd>1){
            if(v[sd-2]<v[sd-1]){
                v.erase(v.begin()+sd-2);
                k--; sd--;
            }
            else break;
        }
    }
    while(k!=0){
        v.erase(v.end()-1);
        k--;
    }
    for(int i=0;i<v.size();i++) answer+=v[i]+'0';
    return answer;
}