백준 2812번 : 크게 만들기

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

2812번: 크게 만들기

 

아이디어 접근은 쉬우나 구현이 까다로웠던 그리디 문제다.

 

입력으로 주어지는 N자리 숫자에서 K개 만큼의 수를 제거하여 만들 수 있는 가장 큰 (N-K)자리 수를 구하는 문제다.

 

처음 생각한 해결 아이디어는 이렇다.  N자리 수를 구성하는 숫자들 중 가장 큰 숫자가 만들어야 하는 수의 첫째 자리로 오는 것이 수를 가장 크게 만들 수 있다. 예를들어 주어진 예시 3번에서 10자리 숫자 중 가장 큰 수는 8이지만, 8을 첫째 자리로 만들기 위해선 8 앞의 7개의 숫자를 모두 지워야 하기때문에 불가능하므로, 그 다음 큰 숫자인 7을 첫째 자리 숫자로 두고 7 앞의 숫자 2개를 제거한다. 이후 7보다 뒤에있는 숫자들 중에서 가장 큰 숫자를 찾아 만들어야 하는 수의 두번째 자리 숫자로 지정한다. 이런 방식으로 자리마다 숫자를 찾으면 가장 큰 수를 찾을 수 있지만 단순히 반복문으로 구현하면 시간초과 판정을 받는다.

 

스택을 이용하여 이 문제를 해결할 수 있다. 입력으로 주어진 수의 맨 왼쪽부터 숫자를 스택에 집어넣는다. 단, 새로 넣으려는 숫자가 스택의 맨 위에 있는 수보다 크면 그 수를 pop한다. 이렇게하면 굳이 매번 가장 큰 숫자를 찾지 않아도 작은 숫자는 제거되고 큰 숫자만 스택에 남게된다. 모든 숫자를 스택에 넣었으면 스택에 들어있는 수를 출력한다. 여기서 주의할 점은 실제 제거된 숫자의 개수가 K보다 작을 수 있다. 그 예시로 54321이라는 수에서 3개의 수를 제거해야할때, 위 방식대로라면 숫자는 제거되지 않고 스택에 모든 숫자들이 들어간다. 그래서 제거한 숫자가 K보다 작다면 추가로 더 제거해야 하는 숫자만큼 스택의 위부터 제거해주면된다.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
s = list(map(int, input().rstrip()))
d = [s[0]]

for i in range(1, n):
    while d and s[i] > d[-1] and k > 0:
        d.pop()
        k -= 1
    d.append(s[i])
print(*d[:len(d)-k], sep='')