[백준 시리즈] 2812번 : 크게 만들기 - 골드3 / Python

2812번 : 크게 만들기

출처 : 백준 /  2812번: 크게 만들기 (acmicpc.net)

사용 알고리즘 : 스택, 그리디

 

문제 설명

N자리 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

 

제한

시간 제한 : 1초 / 메모리 제한 : 128MB

1 <= K < N <= 500,000

 

문제 풀이

1단계 : 최대 시간복잡도는 얼마인가?

N이 50만이므로 O(NlogN) 이하의 알고리즘이 필요하다.

 

2단계 : naive하게 해결해보자

횟수를 모두 사용하더라도 맨 앞자리에 제일 큰 숫자를 배치하는 것이 이득이다. i번째 숫자가 i+1번째 숫자보다 크면 남기고 작으면 지워야한다는 점에서 스택이 연상된다.

 

3단계 : 핵심 아이디어는 무엇인가

넣을 숫자보다 작은 숫자를 K번 이하로 지우면서 스택에 삽입한다. 모든 숫자를 스택에 다 넣었음에도 지울 횟수가 남아있다면, 남은 횟수만큼 pop을 수행한다. 이렇게 하면 O(N)만에 문제를 해결할 수 있다.

 

정답 코드

n, k = map(int, input().split())
num = input()
s = []

for i in num:
    while s and s[-1] < i and k > 0:
        s.pop()
        k -= 1
    s.append(i)

while k>0:
    s.pop()
    k -= 1

print("".join(s))