[백준] 골드4 이중 우선순위 큐

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

7662번: 이중 우선순위 큐

 

이중 우선순위 큐를 구현하여, D -1일때 우선순위가 낮은 숫자를 제거하고, D 1 일때 우선순위가 높은 숫자를 제거할 수 있도록 만드는 문제이다.

당연히 골드문제이기에 시간초과를 고려하여 코드를 효율적이게 짜는 것이 제일 중요했다.

 

우선순위 큐 이기에 heapq를 import하는것을 기반으로 문제풀이를 생각해보았다. heapq의 heappush의 시간복잡도 O(logn)임을 이용하고, 추가적으로 우선순위가 높고 낮음에 따라 효율적이게 지울 수 있는 생각을 하는게 중요했다.

 

처음 문제 풀이는 우선순위큐 heapq와 deque을 사용하였다.

첫번째 풀이(실패)

힙 구조로 입력들을 받아오고, 이를 deque로 변환 후, 시간복잡도 O(1) 비용이 드는 pop 및 popleft를 이용하면 될거라고 생각했다.

하지만, 리스트를 deque로 변환후, 다시 리스트로 변환하는 과정에서 시간복잡도 O(n)이 두번이나 발생하게 된다. 

 

무슨 수를 써서라도 이렇게 푸는건 시간초과로 실패하게 되었다.

 

그래서 min-heap과 max-heap을 만들어서 푸는 방법으로 바꾸었다.

두번째 풀이(실패)

정답을 알고보면, 접근이 거의다 왔는데 아쉬운 부분이 있다.

바로, "동기화"이다.

 

h_max와 h_min을 만들어서 1 혹은 -1일때 삭제연산을 하는건 좋았다.

하지만, h_min에서 지워진게 h_max에서 지워지지 않았을 것이다. 이러한 허점을 보완하기 위해 동기화 작업이 필요한 것이다.

 

그러면 어떻게 동기화를 수행해야하나??? 그게 제일 문제였다. 머갈빡이 제대로 안굴러가서 그런거같기도하고...

세번째 풀이(성공)

마지막 문제풀이는 두번째 풀이와 유사하게 h_max, h_min으로 heap구조를 두개 만들었다.

이후, visited를 만들었다. - 모든 유저들이 이 visited를 이용해서 풀더라...(세번째 풀이 생각할때 답안을 이미 봐버림)

이 visited는 앞서 중요한 키워드였던 "동기화"를 위함이다.

 

heappush에서 h_max와 h_min에 입력을 받은 다음, 해당 입력의 visited 인덱스를 True로 바꾼다.

True의 의미는 내가 입력한 숫자는 h_max든 h_min이든 둘다 존재함을 의미한다.

 

그리고, num == '1'일때는 우선순위가 높은 숫자를 제거해야하는 것이다.

이때 while h_max and not visited(h_max[0][1])의 의미는 max_heap 구조인 h_max의 요소가 존재 하는동안 현재 visited내에서 h_max의 첫번째 요소가 실제로 존재하는지 안하는지 묻는 조건문이다.

 

h_min에서 지워져서 visited내의 인덱스가 False로 되어있는 숫자가 h_max의 첫번째 요소가 될 수도 있다. 

즉, h_min에서 지운 숫자를 h_max에서도 지워지게 하는 동기화 작업인 것이다.

 

while문 뒤에서는 우선순위가 높거나 낮은 숫자를 heappop하고, 해당 숫자를 입력받았던 인덱스를 visited에서 False로 해버린다. 

결국 지워진 숫자이기에 다른 heap에서도 지워져야하기 때문이다.

 

마지막으로, 아직 지워지지 않은 숫자가 min-heap이든 max-heap이든 존재할 가능성을 우려하여 최종적으로 heappop을 진행하였다.

최종 출력을 진행함으로써 코드 구성을 마무리하였다.

 

이렇게 하니깐 어찌됐든 모든 연산의 시간복잡도 O(logn)을 유지하게 되었다.

 

염병

시간복잡도 O(n)이 나오는 순간 절대 풀 수 없도록 이미 시간제한을 셋팅을 해두었기에 짱구를 열심히 굴려야 풀 수 있는 문제였던것 같다.

요즘 풀고 있는 문제들중 답안지를 보고도 이해하기 좀 힘들었던 문제였던것 같았다.

 

1일 1백준 23일째...