[스택] 가장 큰 수

📍 stack

stack: LIFO
나중에 들어간 것이 먼저 나오고,
가장 먼저 들어간 것이 마지막에 나온다.

list 를 사용해서 append(), pop() 을 이용한다.

 

 

📌

입력된 숫자의 자릿수들 중 m개의 숫자를 제거하여 가장 큰 수를 만든다.

(단, 숫자의 순서는 유지한다.)

 

 

<input>

① 5276823 3

 

② 9977252641 5

 

 

✔️ code

 

import sys
sys.stdin=open("input.txt", "r")

n, m=map(int, input().split())
n=list(map(int, str(n)))    #str(n)으로 하나씩 접근해서 숫자로 변환
stack=[]

for i in n:
    #스택이 비어있지 않고
    #숫자가 아직 m개 제거되지 않았고
    #stack에 append() 되는 숫자보다 앞 숫자(stack[-1]) 가 작다면,
    while stack and m>0 and stack[-1]<i:
        stack.pop()
        m-=1
    stack.append(i)

'''
참고

if m!=0:
    #맨 뒤 m개의 자료가 제거된다.
    stack=stack[:-m]

#스택을 string 화
res=''.join(map(str, stack))
print(res)
'''
#반복문이 끝나고 제거할 자릿수가 남아있다면,
while m!=0:
    stack.pop() #stack[-1] 부터 제거해야 한다.
    m-=1

for i in stack:
    print(i, end='')

* 참조는 best code 에 해당

 

# solve:

 

숫자 하나를 자릿수로 접근해야 하기 때문에 str(n) 을 하고 list 에 담는다.

예를 들어 5 2 에서 7 이 append() 되었을 때 5 2 는 7 보다 모두 작기 때문에,

2->5 순서대로 pop() 된다.

반복문이 끝났으나 아직 m이 0이 아니라는 것은 제거해야 할 숫자가 남았다는 뜻이다.

이 때 마지막 두 수가 작은 수 이므로 pop() 시켜준다.

(만약 앞 자리 수보다 컸다면 앞자리가 pop() 되면서 m이 감소했을 것이다.)