[백준 2812번] 크게 만들기 (Python/파이썬)

https://www.acmicpc.net/problem/2812

2812번: 크게 만들기

 

문제를 보자마자 오큰수하고 똑같은 문제라고 생각했다.

예전 포스팅에서 오큰수문제를 다뤘었는데 그때 deque를 사용하여 숫자를 하나씩 빠르게 비교할수 있다는 것을 배웠다.

만들 숫자를 stack에다가 하나씩 넣으면서, 넣어야될 숫자가 먼저 들어간 숫자보다 크면 원래 있던 숫자를 지우고 스택에 숫자를 추가했다. 당연히 들어가고 나서는 그 앞의 숫자들하고도 비교해주어야 하기 때문에 while을 이용하여 똑같은 과정을 반복했다.

 

마지막에 비교가 끝나고 한번도 비교를 안하게 되면 원래 있던 숫자가 그대로 stack에 들어가므로, 남아있는 K의 수만큼 뒤에서부터 지워줬다. (각 자리 숫자가 내림차순으로 되있다는 뜻이므로 그냥 뒤에서부터(작은숫자부터) 지워도 무관하다)

코드는 다음과 같다.

 

import sys
from collections import deque
input = sys.stdin.readline
N, K = map(int, input().split())
num = list(map(int, input().rstrip()))

point = 0
stack = deque([])
stack.append(num[0])
for i in range(1,N):
  while point >= 0 and num[i] > stack[point] and K > 0:
    stack.pop()
    K -= 1
    point -= 1
  stack.append(num[i])
  point += 1
  
while K > 0:
  stack.pop()
  K -= 1
for i in stack:
  print(i, end = "")

 

 

 

 

 

 

오큰수에서 한번 풀어서 그런지 20분 안쪽으로 잘 해결한거 같다.