7662 이중 우선순위 큐
아이디어
OP NUM 형태로 주어지는 일련의 연산을 큐에 넣은 뒤 하나씩 꺼내면서 큐에 연산을 실행하면 된다.
시간 초과
import sys
from collections import deque
input = sys.stdin.readline
def dualQ(operand):
dQ = deque()
while operand:
o, e = operand.popleft()
if o=='I':
dQ.append(e)
elif o=='D' and dQ:
if e==-1:
dQ.remove(min(dQ))
else:
dQ.remove(max(dQ))
return dQ
def sol():
global answer
k = int(input().strip())
operand = deque()
for i in range(k):
o, e = input().strip().split()
operand.append((o, int(e)))
result = dualQ(operand)
answer.append(result)
T = int(input())
answer = []
for t in range(T):
sol()
for q in answer:
if q:
print(max(q), min(q))
else:
print('EMPTY')
두 번째 시도
코드를 작성하면서 I/O의 횟수가 많은게 신경쓰였는데 그 부분이 원인인거같다.
입력을 여러 번 나누어 받지 않고 한 번에 모든 데이터를 입력받은 뒤 정답을 계산하는 방식으로 바꿔보았지만 여전히 시간 초과였다.
import sys
from collections import deque
input = sys.stdin.readline
# operand: deque[(OP, int(n)), ...]
def dualQ(operand):
dQ = deque()
while operand:
o, e = operand.popleft()
if o=='I':
dQ.append(e)
elif o=='D' and dQ:
if e==-1:
dQ.remove(min(dQ))
else:
dQ.remove(max(dQ))
return dQ
answer = []
tc = []
T = int(input())
tc = [deque() for _ in range(T)]
for t in range(T):
k = int(input())
for i in range(k):
o, e = input().strip().split()
tc[t].append((o, int(e)))
result = []
for t in range(T):
result.append(dualQ(tc[t]))
for q in result:
if q:
print(max(q), min(q))
else:
print('EMPTY')
세 번째 시도
진짜 원인 발견
연산의 횟수가 최대 10⁶번이기 때문에 이 문제는 O(N²)으로는 해결할 수 없다.
dualQ 함수 내부에서 min, max함수를 최대 N번 호출하는데 두 함수의 시간복잡도는 O(N)이다.
결국 dualQ의 시간복잡도가 O(N²)였던 것이 문제였다.
dQ에서 최대값, 최소값을 O(1)시간에 찾아서 제거할수 있어야 한다.
import sys
import heapq
input = sys.stdin.readline
# tc: [(OP, int(n)), (OP, int(n)), ...]
def dualQ(tc):
result = []
valid = [False] * len(tc)
minQ, maxQ = [], []
for i in range(len(tc)):
if tc[i][0] == 'I':
heapq.heappush(minQ, (tc[i][1], i))
heapq.heappush(maxQ, (-1*tc[i][1], i))
valid[i] = True
# 이중 우선순위 큐에서 -1 제거 연산
elif tc[i][1] == -1:
# minQ와 maxQ 동기화
while minQ and not valid[minQ[0][1]]:
heapq.heappop(minQ)
# -1 제거 연산 실행(최소값 제거)
if minQ:
valid[minQ[0][1]] = False
heapq.heappop(minQ)
# 이중 우선순위 큐에서 1 제거 연산
else:
# minQ와 maxQ 동기화
while maxQ and not valid[maxQ[0][1]]:
heapq.heappop(maxQ)
# 1 제거 연산 실행
if maxQ:
valid[maxQ[0][1]] = False
heapq.heappop(maxQ)
# 동기화되지 않았을수 있는 연산항 동기화
while minQ and not valid[minQ[0][1]]:
heapq.heappop(minQ)
while maxQ and not valid[maxQ[0][1]]:
heapq.heappop(maxQ)
return minQ
answer = []
tc = []
T = int(input())
tc = [[] for _ in range(T)]
for t in range(T):
k = int(input())
for i in range(k):
o, e = input().strip().split()
tc[t].append((o, int(e)))
result = []
for t in range(T):
result.append(dualQ(tc[t]))
for q in result:
if q:
print(max(q)[0], min(q)[0])
else:
print('EMPTY')
최소, 최대값을 O(1)시간에 찾아 제거하도록 수정했지만 버퍼링 방식 때문에 메모리 제한을 초과했다.
네 번째 시도 (정답)
입력을 받는 즉시 답을 출력하도록 바꿔 메모리 사용량을 줄였다.
import sys
import heapq
input = sys.stdin.readline
# op: [(operator, n), (operator, n), ...]
def calcDualQ(op):
maxH = [] # maxH[0]: 항상 최대값
minH = [] # minH[0]: 항상 최소값
valid = [False] * len(op) # maxH, minH 사이의 일관성 유지
for i in range(len(op)):
# I
if op[i][0] == 'I':
heapq.heappush(maxH, (-1*op[i][1], i))
heapq.heappush(minH, (op[i][1], i))
valid[i] = True
# D -1(최소값 제거)
elif op[i][1] == -1:
# dirty check: maxH에서 삭제한 내용을 minH에 반영
while minH and not valid[minH[0][1]]:
heapq.heappop(minH)
# 최소값 제거
if minH:
valid[minH[0][1]] = False
heapq.heappop(minH)
# D 1
else:
# dirty check: minH에서 삭제한 내용을 maxH에 반영
while maxH and not valid[maxH[0][1]]:
heapq.heappop(maxH)
# 최대값 제거
if maxH:
valid[maxH[0][1]] = False
heapq.heappop(maxH)
# dirty check
while maxH and not valid[maxH[0][1]]:
heapq.heappop(maxH)
while minH and not valid[minH[0][1]]:
heapq.heappop(minH)
if maxH:
print(-1*maxH[0][0], minH[0][0])
else:
print('EMPTY')
# testcase 개수 T
T = int(input().strip())
for i in range(T):
# 연산의 개수 k
k = int(input().strip())
op = [] # k개의 연산 저장
for j in range(k):
operator, n = input().strip().split()
n = int(n)
op.append((operator, n))
# 모든 연산을 계산하고 결과 출력
calcDualQ(op)
Comments