[백준 2812번] 큰 수 더하기 (python)

문제

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

 

기록

(greedy 7일차) 난장판....ㅎㅎ 시간초과를 해결하기위해 내가 구현한 방법과 다른 방법을 사용해야했다. 기존엔 인덱스부터 K+1개까지 범위 내의 최댓값을 찾고 앞부분을 지우는 과정을 반복했다. 이 방법은 최댓값이 가장 앞에 있을 때 비슷한 범위를 중복되게 탐색해야한다는 점에서 시간초과에 걸렸던 것 같다. 따라서 숫자를 한 번 돌면서 stack을 사용해 내림차순이 되도록 크기비교하며 K개 제거한다.

 

이 문제의 해결방법은 결과숫자가 가능한 큰 숫자부터 내림차순으로 될 수 있도록 맨 앞부터 K개를 지워나가야한다는 것. 시간초과에 걸리지 않도록 최대한 탐색범위가 적은 구현방법을 찾는 것도 중요하다.

 

코드

N, K = map(int, input().split())
num = list(input())

newnum = []
size = N-K
for i in range(N):
    while K > 0 and newnum and newnum[-1] < num[i]:
        newnum.pop()
        K -= 1
    newnum.append(num[i])

print(''.join(newnum[:size]))

제거할 숫자 K가 남아있는 동안은 결과숫자(newnum)가 최대한 내림차순으로 유지될 수 있도록 현재숫자와 결과숫자의 뒤부터 비교하여 크다면 지우고 현재숫자를 추가한다. 숫자를 제거할 때마다 K를 1씩 줄인다.

 

기존 숫자가 내림차순으로 되어있는 경우, K개를 다 지우지 못할 수 있기 때문에 마지막에 N-K까지 범위를 출력한다.