용이 산다 (3430번) - 백준 (BOJ)

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

3430번: 용이 산다

 

 

백준 - 용이 산다 (Enter The Dragon) (3430번)

 

난이도 : Gold 1

알고리즘&자료구조 : 우선순위 큐 (Priority Queue) & 그리디 (Greedy)

시간복잡도 (Time Complexity) : O( nlogn )

---

★ 핵심 Idea ★

 

◎ 특정 호수 "x"에 시간 "t" 에서 비가 내렸다고 하면,

"t" 시점 전의 비가 오지 않은 날에는, "t"에서 내린 비를 먹을 수 없다.

 

따라서 시점 0부터 하루씩 탐색하면서,

현재 시점에서 각 호수 별로, 해당 호수에 비가 내리는 가장 가까운 미래 시점을 우선순위 큐에 넣어준다.

 

 

< 전체 코드 >

 

import sys
input = sys.stdin.readline
from heapq import heappop, heappush


class Ardenia():
    def __init__(self, n, m):
        pq = []
        lake_idx = [[] for _ in range(n+1)]
        query = list(map(int, input().split()))

        is_full = [True] * (n+1)
        for i in range(m-1, -1, -1):
            lake_idx[query[i]].append(i)
        for i in range(1, n+1):
            if lake_idx[i]:
                heappush(pq, lake_idx[i].pop())
        
        is_poss = 'YES'
        suck_up = []
        for lake in query:
            if not lake:
                if pq:
                    i = heappop(pq)
                    suck_up.append(query[i])
                    is_full[query[i]] = False
                else:
                    suck_up.append(0)
            else:
                if is_full[lake]:
                    is_poss = 'NO'
                    break
                is_full[lake] = True
                if lake_idx[lake]:
                    heappush(pq, lake_idx[lake].pop())

        self.result = (is_poss, suck_up)


if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        village = Ardenia(*map(int, input().split()))
        print(village.result[0])
        if village.result[0] == 'YES':
            print(*village.result[1])