문제

풀이

방법 : 큰 수를 만날 때 까지 index를 넘기다 큰 수를 만나면 큰 수의 직전 수를 제거함.
ex) 1) 4177252841 > 2) 477252841 > 3) 77252841 > 775841

문자열로 풀다가 시간초과 나서 스택으로 해결함.
1. alive, dead, num 3가지 배열을 사용함.
2. 일단 무조건 alive stack이 비어있으면 num[0]를 popleft해서 alive에 append 해줌.
3. 그리고 alive[-1]과 num[0]를 비교해줌.

• alive[-1] >= num[0] : 큰 수를 못 만났기 때문에 num[0]를 popleft해서 append 해줌.
• alive[-1] < num[0] : 큰 수를 만났기에 alive[-1]을 pop하여 dead로 append 해줌.

4. 이렇게 pop하면서 while문의 조건을 만족시키면 dead를 제외한 alive + num을 print해주면 됨.

하지만, 위 코드는 n, k = 3, 2 / 523 같은 num이 판단을 미쳐 다 하기전에 비워지는 반례가 생김. 따라서 num의 크기가 0이 되면, alive에서 k - dead만큼 alive에서 pop하여 dead에 추가해줌.
(∵ num이 빌때까지 dead를 못 채웠단 소리는 큰 수를 계속 못 만났다는 소리고, 이는 곧 alive가 내림차순으로 구성되어 있음을 알 수 있음. 따라서, dead의 부족 분 만큼 pop을 해주면 가장 큰 수를 얻을 수 있음.)

코드

import sys
from collections import deque
def solution() :
    n, k = map(int, sys.stdin.readline().split())
    num = deque(list(input()))
    
    alive = []
    dead = []
    
    while len(dead) != k :
        if len(num) == 0 :
            for _ in range(k - len(dead)) :
                alive.pop()
            break
        if len(alive) == 0 :
            alive.append(num.popleft())
        else :
            if alive[-1] >= num[0] :
                alive.append(num.popleft())
            else :
                dead.append(alive.pop())
    
    print(''.join(alive + list(num)))
                
solution()