2812 백준 파이썬

생각보다 많이 어려웠던... 상상도 못했던 방법으로 해결했던 문제

처음 풀이는 재귀로 했더니 시간복잡도때문에 시간초과가 발생했다.

def do(rest,ans,start):
    mmax=0
    ch=0
    if rest==0:
        return ans
    else:
        for x in range(start,len(num)):
            if x+rest<=len(num) and mmax<num[x]:
                mmax=num[x]
                ch=x+1
        ans.append(mmax)
        return do(rest-1,ans,ch)
n,k=map(int,input().split())
num=list(map(int,list(input())))
ans=do(n-k,[],0)
for x in ans:
    print(x, end='')

알고보니 그냥 스택으로 해결하면 됐던 문제....

#https://www.acmicpc.net/problem/2812
import sys
N,K = map(int,sys.stdin.readline().split())
nums = list(map(int,sys.stdin.readline().strip()))
result = []
rest= K
for i in range(N):
    while rest>0 and result:
        if result[len(result)-1] < nums[i]:
            result.pop()
            rest-=1
        else:
            break
    result.append(nums[i])
for x in range(N-K):
    print(result[x], end="")