[파이썬/알고리즘] 스택을 활용한 가장 큰 수 문제

파이썬을 이용한 가장 큰 수 구하기 문제

문제) 주어진 숫자의 자릿수에서 m개의 수를 제거해서 가장 큰 수를 만드는 프로그램을 작성하라.

입력

10진수 n과 제거해야할 자릿수의 개수 m이 주어진다.

풀이

n, m = map(int, input().split())
n = list(map(int, str(n)))  #숫자n을 스트링으로 바꿔야 하나씩 접근 가능.
stack=[]
for x in n:
   while stack and m>0 and stack[-1]<x:  #stack이 비어있지 않고, stack의 마지막 자릿수가 더 작으면 pop
      stack.pop()
      m -= 1
   stack.append(x)
if m!=0:
   stack=stack[:-m]

예시)

n = 9977252641, m = 5

맨 앞에서부터 스택에 채워넣는다.

자신의 앞에 있는 숫자가 자신보다 작으면 꺼낸다(pop)

 

스택: 9 9 7 7 6 4 1

5 -> 앞에 2를 제거

6 -> 앞에 2, 5 제거

 

3개밖에 제거 못했기 때문에, 뒤에서 2개를 더 제거한다.(내림차순이 되어 있기 때문에.)

stack[:-2]

 

참고)

https://study3.tistory.com/6

[자료구조] 스택, 큐

출력

#결과출력방법1
res=''.join(map(str,stack))
print(res)

#결과출력방법2
for x in stack:
   print(x, end='')