[백준] 크게 만들기

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

2812번: 크게 만들기

 

heapq 를 이용하여 처음에 올 수 있는 자리에 수 중 가장 큰 것을 뽑고 index 를 비교하여 다음으로 올 수 있는 수 중에서 가장 큰 값을 차례대로 뽑으면 된다.

 

예를 들어, N = 10, K = 4, number = 4177252841 라고 하자.

그럼 가장 처음에 올 수 있는 수는 417(1)7(2)2 중 하나의 수가 된다. 52841 중 하나를 택하면 6자리의 수가 될 수 없다.

가장 큰 값인 7과 7의 인덱스(I)를 잡는다. 다음으로, 417(1)7(2)25 중의 하나를 택하는데 인덱스를 비교하여 I 이하의 숫자들은 버리고 7(2)25 중의 하나를 택하여 주면 된다. number의 마지막 숫자까지 queue 에 하나를 넣고 I 보다 큰 숫자 하나를 뽑아 답을 완성해준다.

 

import sys
import heapq

N, K = map(int, sys.stdin.readline().split())
number = str(sys.stdin.readline().strip())
queue = []
answer = []

for i in range(K + 1):
    heapq.heappush(queue, [-int(number[i]), i])

M, I = heapq.heappop(queue)
answer.append(str(-M))

for i in range(N - K - 1):
    heapq.heappush(queue, [-int(number[K + 1 + i]), K + 1 + i])
    m, j = 0, -1

    while j < I:
        m, j = heapq.heappop(queue)

    I = j
    answer.append(str(-m))

print(int(''.join(answer)))