[Python 3] BOJ - 2812 "크게 만들기"

 # 문제 링크

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

2812번: 크게 만들기

 

 # 풀이

 개인적으로 이 문제의 핵심은 그리디 알고리즘과 스택이라고 생각한다. 문제를 풀기 전에 간단한 다른 문제를 풀어보자. 0이상 9이하의 어떤 n개의 수가 주어지고, n개의 수를 모두 사용하여 n자리 숫자를 만들때 가장 크게 만드는 방법은 무엇인가? 당연히 큰 수부터 채워나가는 것이다. 따라서, 우리는 n개가 아니라 n-k개를 이용하는 것이지 문제의 큰 틀은 바뀌지 않았음을 알 수 있다. 

 그런데 아무렇게 k개를 제외하면 정답을 구할 수 없다. 그런데 우리는 가장 큰 수가 가장 왼쪽에 오길 원한다. 따라서, 자신보다 왼쪽에 있는 수 중에서 자신보다 작은 수가 있다면 그런 수는 남은 횟수 안에서 지워주는 것이 이득이다. 이것은 단조 감소 스택을 이용하면 쉽게 구현가능하므로 스택을 이용하면 시간안에 정답을 구할 수 있다.

 주의할 점은 단조감소 스택을 이용해도 k가 0이 아닐 수도 있다. 즉, 이미 주어진 수가 단조감소하는 수열로 주어진 경우거나 그렇지 않아도 k개보다 적게 써도 전체를 단조감소하게 만들 수 있는 경우이다. 따라서 더이상 단조감소를 만들 수 없고 문제에서 k가 0이 될 때까지 숫자를 제외해야 하므로 그냥 뒤에서부터 k개를 잘라주면 정답을 구할 수 있다

 

 # 코드

import sys

# 입력부
n, k = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().rstrip()))

# st : 단조감소 스택
st = []
idx = 0

while idx < n:
	# k가 0이하면 더이상 단조감소 스택을 만들 수 없으므로 break
    if k <= 0:
        break
    if not st:
        st.append(arr[idx])
    else:
        while st and st[-1] < arr[idx] and k > 0:
            k -= 1
            st.pop()
        st.append(arr[idx])
    idx += 1

# 끊어진 idx부터 n까지 남은 수를 저장
for i in range(idx, n):
    st.append(arr[i])
    
# 단조 감소 스택을 만들고도 남았다면, 마지막 k자리를 잘라냄
if k:
    size = len(st)
    st = st[:size - k]
    
# 정답 출력
print(''.join(map(str, st)))