파이썬으로 스택을 사용하여 문제 풀기-1

문제

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어지고, (1<=K<N<=500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

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

answer=[]
count=k
for num in number:
    while answer and count>0 and answer[-1]<num:#answer 스택이 비어 있지 않고 지울 수 있는 횟수 k가 남아있고, answer의 마지막 값이 num보다 작다면 answer의 마지막 값을 지운다.
        del answer[-1]
        count-=1
    answer.append(num)#현재 순회 중인 값 num을 answer에 추가한다.
    
print(''.join(answer[:n-k]))

 

맨 앞의 숫자가 클수록 가장 큰 수를 얻게 된다.

스택을 사용하여 수를 지워 시간복잡도를 감소시켰다.

 

 

해석

현재 인덱스 위치값보다 현재 인덱스 -1 위치값이 작을 때, 지울 수 있는 횟수가 남아있다면 지워준다.

 

시간복잡도를 줄이기 위해 새로운 변수 answer를 만들고 배열을 순회할 때마다 answer에 그 값을 추가한다.

그리고 answer의 마지막 값보다 현재 순회 중인 배열의 index값 num이 크다면 answer의 마지막 값을 지워보자.