Python - [백준 23326 시간초과] 홍익 투어리스트 (자가균형트리, 우선순위큐)

 

 

우선순위 큐로 구현했으나 최소값 탐색 과정에서 반복구간이 발생해 시간복잡도가 O(N)이 되었습니다.

구현은 되었으나 시간복잡도를 해결하지 못한 케이스네요

방법을 아직 찾지 못해 미제로 남깁니다..

 

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

 

 

 

 

 

"""
python_boj_23326_홍익 투어리스트
https://www.acmicpc.net/problem/23326

1 i: i$번 구역이 명소가 아니었다면 명소로 지정되고, 명소였다면 지정이 풀리게 된다.
2 x: : 도현이가 시계방향으로 x만큼 이동한다.
3 : 도현이가 명소에 도달하기 위해 시계방향으로 최소 몇 칸 움직여야 하는 지 출력한다. 명소가 존재하지 않는 경우 
$-1$을 출력한다.

loc 위치 -- 기준 도현이 위치로 재배열
valid 딕셔너리 KEY 위치 VALUE 명소여부
도현이의 이동 = 원형 큐 (current + x) % N

시간 초과
query 3을 처리할 때 N번 반복
"""

import sys
import heapq
input = sys.stdin.readline

N, Q = map(int, input().strip().split())

valid = {}
loc = list(map(int, input().strip().split()))
for l in range(N):
    valid[l] = loc[l]

current = 0

for _ in range(Q):
    # QUERY 1,2,3

    query = list(map(int, input().strip().split()))

    if query[0] == 1:
        index = query[1] -1
        if valid[index] == 0:
            valid[index] = 1
        else:
            valid[index] = 0
    elif query[0] == 2:
        current = (current + query[1]) % N
    else:
        heap = []
        for v in valid:
            if valid[v] == 1:
                heapq.heappush(heap, (v - current + N) % N)
        if len(heap) == 0:
            print(-1)
        else:
            distance = heapq.heappop(heap)
            print(distance)