[백준 2812] 크게 만들기 (C++)

문제 링크: www.acmicpc.net/problem/2812

2812번: 크게 만들기

1. 주의할 점

- 스택 or 그리디를 이용하여 해결한다

- 본인이 생각한 특수 TC 이외에도 많은 특수 TC가 존재한다

##일부 TC
#1
6 2
391123
//output : 9123

#2
6 2
436436
//output : 6436

#3
7 3
7654321
//output : 7654

#4
6 2
362514
//output : 6514

#5
2 1
19
//output: 9

#6
7 2
9543543
//output: 9554

 

2. 구현

- String형태가 아닌 Char형태의 배열을 통해 값을 입력 받도록 한다

- 가장 처음의 숫자는 그대로 Arr[] 배열에 담는다

- 위의 TC 6번을 통해, 같은 숫자를 삭제해야할 때 앞에 나타나는 숫자부터 지워야 하는 것을 알 수 있다

- 두번째 숫자부터 비교를 시작하며, 배열 + Tail 인덱스를 이용하여 스택을 구현한다

- 현재 지울 수 있는 횟수가 남아있으며, 스택이 비어있지 않고(Tail>0) 스택의 Top보다 현재 값이 더 크다면 Stack을 Pop시킨다

- Pop을 수행할 때마다 Tail--와 Err--를 수행한다(Pop효과 + 남은 삭제 수 1 감소)

- 위의 과정을 조건에 부합하지 않을 때까지 반복한다

- Arr[]의 배열을 출력시키며, 입력받은 길이 - 지운 길이만큼 출력한다

#include <iostream>
using namespace std;
char arr[500000];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int len, err, tail=1,tmp;
    cin >> len >> err;
    tmp = err;
    char c;
    cin>>arr[0];
    for(int i=1;i<len;i++){
        cin >> c;
        while(err && tail>0 && arr[tail-1]<c){
            tail--;
            err--;
        }
        arr[tail++]=c;
    }
    for(int i=0;i<len-tmp;i++)
        cout<<arr[i];
    return 0;
}