백준 7662. 이중 우선순위 큐
사용 언어: python 3.9.1
❓ Problem
📕 피드백
1. 발전 방향
문제를 읽으면서 반례가 될 만한 부분들을 차근차근 기록해 나가야 할 것 같음.
2. 느낀점
메모리 초과 때문에 어떤 변수에 미리 한꺼번에 저장해두고 쭉 진행하는 것보다는, for문을 진행하면서 input을 따로 분산해서 받는 게 더 나을 듯.
🚩 Solution
1. 접근법
TRY 1
식별자로 안했고, info를 dict형으로 : key=큐의정수
, val=0 if (삭제된 적 있는 경우) else 1
으로 구현했는데, 같은 정수가 다른 데이터로 삽입/삭제되는 경우가 있음을 본문에서 명시했었다..
TRY 2
그래서 반례를 적용해서 info
를 리스트로 하되, 길이를 k개로 둬서 최대한 메모리에 낭비가 없도록 했다. 이때 info
에서 key=식별자, 즉 정수가 같아도 서로 다른 명령어로 들어왔으면(I 32, I 32) 서로 식별할 수 있는 식별자로 info
에 삽입할 수 있게 했다. 이때 식별자는 '지금까지 수행한 명령어 개수'로 for문의 i로 설정했다.
TRY 3
그렇게 반례를 해결해도 계속 메모리 초과가 나서
-
우선 삭제 명령이 들어왔을때
x = heapq.heappop()
으로 매번 pop되는 값들을 저장해 뒀었는데 그걸 그냥heaqp.heappop()
으로 버리는 걸로 처리: 10%? 정도까지 진행하다가 메모리 초과 뜸
-
그래도 계속 메모리 초과가 떠서
commands = list(map())
이렇게 I나 D에 관련한 명령들을 한꺼번에 받았던 걸 →c = readline().split()
으로 for문에 나눠서 받았다.: 메모리 초과 해결!
2. 코드
import sys, heapq
T = int(sys.stdin.readline()); ans = []
for _ in range(T):
k = int(sys.stdin.readline())
maxq = []; minq = []; info = [False]*k
for i in range(k):
# 명령마다 처리
c = sys.stdin.readline()[:-1].split()
if c[0] == 'I':
# * INSERT
heapq.heappush(maxq, (-1 * int(c[1]), i))
heapq.heappush(minq, (int(c[1]), i))
info[i] = True
else:
# * POP
if int(c[1]) == 1 and len(maxq) != 0:
# 최댓값 삭제
while(maxq and not info[maxq[0][1]]):
heapq.heappop(maxq)
if maxq: info[maxq[0][1]] = False; heapq.heappop(maxq)
elif int(c[1]) == -1 and len(minq) != 0:
# 최솟값 삭제
while(minq and not info[minq[0][1]]):
heapq.heappop(minq)
if minq: info[minq[0][1]] = False; heapq.heappop(minq)
# 마지막 max_val, min_val
while(minq and not info[minq[0][1]]): heapq.heappop(minq)
while(maxq and not info[maxq[0][1]]): heapq.heappop(maxq)
ans.append('%d %d'%(-1*maxq[0][0], minq[0][0]) if maxq and minq else "EMPTY")
for a in ans:
print(a)
3. 결과
시간 복잡도 분석
O(b*loga), b=삽입명령개수, a=삭제명령개수
Author And Source
이 문제에 관하여(백준 7662. 이중 우선순위 큐), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@tera_geniel/백준-7662.-이중-우선순위-큐저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)