프로그래머스 - 이중우선순위큐
문제
https://programmers.co.kr/learn/courses/30/lessons/42628
두 개의 우선순위큐를 이용하여 최소 최대 상태를 유지한다.
- Que 1, 최소큐 : 최소값을 얻기 위한 큐
- Que 2, 최대큐 : 최대값을 얻기 위한 큐 (음의 부호를 붙여 최댓값을 구할 수 있도록 한다.)
두 개의 map을 이용하여 이미 pop한 노드들을 기록한다.
- Check 1 : 최대큐에서 삭제한 노드를 최소큐에서 중복되어 삭제하지 않도록 기록한다.
- Check 2 : 최소큐에서 삭제한 노드를 최대큐에서 중복되어 삭제하지 않도록 기록한다.
예를 들어, I 2 / I -3 / I -3 / I -3 / D -1 / D -1 이런 명령어가 주어졌을 때, 첫 번째 삭제 명령이 들어오기 전까지의 큐 상태는
- 최소큐 : [ -3, -3, -3, 2]
- 최대큐 : [-2, 3, 3, 3]
D -1 이므로 최소큐에서 pop하게 되면 -3이 삭제되어 최소큐는 아래와 같이 된다.
- 최소큐 : [-3, -3, 2]
그러나 최소큐와 최대큐는 사실 하나의 큐의 상태를 나타내고 있다. 그래서 최대큐에게 -3이 삭제되었다고 알려주어야 한다. 그러한 기록을 하는 것이 map(check변수)이다. key : value = 삭제한 노드의 값(반대 부호) : 횟수를 의미한다. 노드의 값을 key로 하여 value를 조회했을 때
check[value] =
- 디폴트 값인 0 : 삭제된 적이 없다는 것을 의미
- 양수 : 이전에 이미 삭제된 횟수를 의미
여기서는 최소큐에서 -3을 삭제하였으니 이는 최대큐에서 3이라는 노드 하나를 삭제한 것과 같다. 따라서 check 2 맵의 3을 key로 가지는 값을 하나 증가시켜 준다. (디폴트 값은 0으로 설정)
1
check2[-value] += 1
예를 들면 이런식으로 삭제했다는 것을 반대편의 큐에게 알려주는 것이다. 반대로 최대큐에서 -2를 삭제했다면 사실상 2라는 노드를 제거한 것이므로 최소큐에게도 알려주어야 한다.
이러한 check라는 map은 pop해야할 대상을 찾는 과정에서 사용된다. D 1 명령이 들어올 경우 바로 que2.pop() 하게 된다면 가장 앞에 있던 노드가 다른 큐에서 이미 삭제한 노드일 수도 있기 때문이다. 따라서 while문을 돌면서 우선순위큐의 가장 앞쪽 노드가 이미 삭제된 적이 있는지를 계속 검사하면서 삭제되지 않은 노드를 찾을 때까지 반복문을 계속하는 것이다. while문이 끝나면 삭제할 대상을 찾은 것이다. 대상을 찾았으니 위와 같이 다른 큐에게 삭제한 내용을 알려주고 마지막으로 pop을 하면 된다.
I (value)- 최소큐에는 양의 절댓값을, 최대큐에는 음의 절댓값을 삽입한다.
D 1: 최댓값을 삭제한다.- 최대큐에서 pop하면서 pop할 대상을 찾는다.
- 이미 pop한 노드인 경우 건너뛴다.
- 최댓값을 최대 큐에서 삭제한다
- 삭제한 노드의 양의 절댓값을 최소큐에 표시한다.
D -1: 최소값을 삭제한다.- 최소큐에서 pop하면서 pop할 대상을 찾는다.
- 이미 pop한 노드인 경우 건너뛴다.
- 최소값을 최소큐에서 pop한다.
- 삭제한 노드의 음의 절댓값을 최대큐에 표시한다.
파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import heapq
from collections import defaultdict
def solution(operations):
answer = [0,0]
que = [[],[]] # que[0] = 최소힙, que[1] = 최대힙
heapq.heapify(que[0])
heapq.heapify(que[1])
checked = [defaultdict(int), defaultdict(int)] # 삭제된 노드들을 기록하기 위한 각 큐의 기록 map
cnt = 0 # cnt는 큐에 남아있는 노드의 개수를 의미한다.
for op in operations:
cmd, val = op.split()
val = int(val)
if cmd == 'I':
cnt += 1
heapq.heappush(que[0], val) # 최소큐에는 양의 절댓값을 삽입
heapq.heappush(que[1], -val) # 최대큐에는 음의 절댓값을 삽입
else:
if cnt == 0:continue # 큐에 남아있는 노드가 없으므로 삭제 명령 무시
cnt -= 1
if val < 0: # 최소값 삭제 명령
while checked[0][que[0][0]] > 0: # 삭제된 적이 없는 노드를 찾을 때까지 반복문 실행
checked[0][que[0][0]] += -1
heapq.heappop(que[0])
checked[1][-que[0][0]] += 1 #최대큐에게 삭제할 대상을 알려줌
heapq.heappop(que[0]) #최소큐의 가장 앞노드 삭제
else: # 최댓값 삭제 명령
while checked[1][que[1][0]] > 0:
checked[1][que[1][0]] += -1
heapq.heappop(que[1])
checked[0][-que[1][0]] += 1 # 최소큐에게 삭제할 대상을 알려줌
heapq.heappop(que[1]) # 최대큐의 가장 앞노드 삭제
# que[0]에서는 최소값을, que[1]에서는 최댓값을 찾는다.
while que[0] and checked[0][que[0][0]] > 0:
checked[0][que[0][0]] += -1
heapq.heappop(que[0])
if que[0] != []:
answer[1] = que[0][0]
while que[1] and checked[1][que[1][0]] > 0:
checked[1][que[1][0]] += -1
heapq.heappop(que[1])
if que[1] != []:
answer[0] = -que[1][0]
return answer
추가
프로그래머스에서 코드를 실행해보면 맞다고 나오는데 테스트 케이스가 적어서 좀 불안하다. 엣지 케이스가 더 많이 주어질 경우에 pop할 대상을 찾는 while문 부분에서 list out of index 에러가 날 것 같다.