[백준 14427번] 수열과 쿼리 15 (Python3)

import sys
input = sys.stdin.readline
import heapq

N = int(input())
data = [0]+[*map(int,input().split())]

hq = []
for i in range(1,N+1):
  heapq.heappush(hq,(data[i],i))

for _ in range(int(input())):
  Q = [*map(int,input().split())]
  if Q[0] == 1:
    q,i,v = Q
    data[i] = v
    heapq.heappush(hq,(v,i))
  else:
    while data[hq[0][1]] != hq[0][0]:
      heapq.heappop(hq)
    print(hq[0][1])

간단한 우선순위 큐 문제.

 

1. 모든 데이터를 인덱스와 함께 힙큐에 넣어준다.

2. 데이터가 바뀔 때마다 힙큐에 새로 넣는다.

3. 데이터를 출력할 때는 유효한 데이터인지 확인한다. 현재의 데이터와 같은 값인지 확인하면 된다.

4. 유효하지 않은 경우 heappop해서 제거, 유효하면 출력한다.

 

세그먼트 트리로 푼 사람들도 많은 것 같아 보이는데, 이 문제는 특정 구간에서의 최솟값을 구하는 문제가 아닌 전체 데이터에서 최솟값을 출력하는 문제이기 때문에 세그먼트 트리를 쓸 필요가 전혀 없다.