백준 2812 크게 만들기

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

2812번: 크게 만들기N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.www.acmicpc.net

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

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

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

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

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

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

끝까지 다 돌았는데도 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-=1print(''.join(stack))

뿌듯하다