백준 2812 크게 만들기

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

2812번: 크게 만들기

 

스택 알고리즘 강의를 들었던게 도움이 되었다.

내 혼자힘으로 푼 몇안되는 골드문제중 1

 

1. 숫자를 문자 리스트로받아 하나씩 떨어뜨려놓는다.

 

2.반복문을 돌면서, 앞에부터 1개씩 스택에 추가한다.

!!! 만일 추가할 숫자가 스택의 마지막(-1)보다 작다면, 스택마지막이 추가할 숫자보다 클때까지, 혹은 스택이 없을때까지, 혹은 k가 0일때까지  pop()해준다.

총 k개까지 제거할 수 있으므로, pop할때마다 k를 1씩 빼주고 0이 되면 종료한다.!!!

 

 

3. 끝까지 다 돌았는데도 k가 남아있을수도 있다. 이러면 스택은 최소 비오름차순일 것이다.  그러므로 k번 pop을 해주면 된다.'

4.출력

 

##'1'은 '2'보다 작으므로, 굳이 int변환을 해주지 않아도 계산이 가능하다##

 

%%코드%%

n,k =map(int,input().split())
number=list(input())
stack=[]

for i in range(len(number)):
    tmp=number[i]
    while stack and stack[-1]<tmp and k>0:
        stack.pop()
        k-=1
        if n==0:break
    stack.append(number[i])
while k >0:
    stack.pop()
    k-=1


print(''.join(stack))

뿌듯하다