1. 가장 큰 수(스택)

가장 큰 수 

 

선생님은 현수에게 숫자 하나를 주고, 해당 숫자의 자릿수들 중 m개의 숫자를 제거하
여 가장 큰 수를 만들라고 했습니다. 여러분이 현수를 도와주세요.(단 숫자의 순서는
유지해야 합니다)
만약 5276823 이 주어지고 3개의 자릿수를 제거한다면
7823이 가장 큰 숫자가 됩니다.

▣ 입력설명
첫째 줄에 숫자(길이는 1000을 넘지 않습니다)와 제가해야할 자릿수의 개수가 주어집니다.

▣ 출력설명
가장 큰 수를 출력합니다.

▣ 입력예제 1
5276823 3

▣ 출력예제 1
7823

▣ 입력예제 2
9977252641 5

▣ 출력예제 2
99776

 

문제풀이

import sys
sys.stdin=open("input.txt", "r")
num, m=map(int, input().split())

num = list(map(int, str(num))) #숫자 n을 한자리씩 리스트에 저장하기 위한 조치

stack=[]                      #숫자를 담기 위한 stack 


for x in num:  
   while stack and m>0 and stack[-1]<x:       # while stack 의 의미: "stack에 data가 있으면"    
        stack.pop()                           # while 문이 핵심
        m -=1
   stack.append(x)

if m>0:
  stack = stack[0:-m]  #

res =''.join(map(str, stack))
print(res)

 

 

Hint

1. 자리수에 위치한 숫자(자신)입장에서!

    나(숫자)보다 앞쪽에 작은 애들은 아웃시킨다.

 

2.  아웃시켰음에도 불구 하고, 숫자를 더 아웃시켜야 된

     다면, 스택에 숫자가 들어찼을 때 내림차순이 되므로

     끝에서부터 작은 숫자를 추가적으로 아웃시켜주면 된다.

 

 

사전지식(암기사항)

 1. Stack : LIFO (가장 최근에 넣은 것이 먼저 나온다.)

            파이썬의 경우 리스트에서 append하고 pop하면 스택 구조가 된다.

 

 2. append() : 마지막 자리에 요소 추가

 

 3. pop():  Argument를 넣지 않는 경우 마지막자리의 요소를 반환한다.

 

 

보충설명

리스트 인덱스

 

stack [ 0: -2] : -2직전인 0부터 -3까지 슬라이싱     출력결과  [ 9, 9, 7, 7, 6 ]

 

stack [1:4] : 4 직전인 1~3까지 슬라이싱                출력결과 [ 9, 7, 7 ]