가장 큰 수(스택)

인프런 김태원님의 파이썬 알고리즘 문제풀이를 듣고 작성한 글입니다.

https://inf.run/Uiep

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의

 

#강의 풀이
num, m = map(int, input().split())
num = list(map(int, str(num)))
stack = []
for x in num:
    while stack and m>0 and stack[-1]<x:
        stack.pop()
        m -= 1
    stack.append(x)
if m != 0:
    stack = stack[:-m]
res = ''.join(map(str, stack))
print(res)

이 문제를 stack 자료구조를 이용하여 푸는 문제입니다.
5276823을 예로

반복문을 돌면서 5를 스택에 넣고

stack = [ 5 ]

다음 숫자 2가 5보다 작다면 2도 넣습니다.

stack = [ 5, 2 ]

그 이후 7을 넣는데, 스택에 저장된 값들이 모두 7보다 작다면 stack.pop을 합니다.

2는 7보다 작으므로 pop되고, m -= 1 합니다.

stack = [ 5 ] ,    2는 pop   ,    m = 2

5는 7보다 작으므로 pop되고, m -=1 합니다.

stack = [ ] ,    5는 pop  ,   m = 1

앞에 숫자가 없으므로 7을 append 합니다.

stack = [ 7 ]

이러한 과정을 반복하면 m = 0 이 되어 while문을 탈출하고 

stack = [ 7, 8, 2, 3]  이 저장됩니다.

 

예제 2번에서는

m 이 2인 상태로 for문이 종료되기 때문에

마지막 2숫자를 뒤에서부터 제거하기 위해

슬라이싱을 사용해줍니다.