백준 7662 이중 우선순위 큐

max힙과 min힙을 둘다 적절히 사용해주면 될것같다.

import sys
import heapq
t=int(sys.stdin.readline().rstrip())
for _ in range(t):
    n=int(sys.stdin.readline().rstrip())
    max_h=[]
    min_h=[]
    size=0
    for i in range(n):
        opcode,num=sys.stdin.readline().rstrip().split()
        num=int(num)
        if opcode=='I':
            heapq.heappush(min_h,num)
            heapq.heappush(max_h,-1*num)
            size+=1
        else:
            if size==0:
                continue
            size-=1
            if num==1:
                heapq.heappop(max_h)
            else:
                heapq.heappop(min_h)
    if size==0:
        print("EMPTY")
    else:
        print(-1*max_h[0],min_h[0])

이렇게 작성했다.

size가 0이 될때 모든 힙을 비워줘야한다.

분명 설계할때는 생각을 했었는데 왜 코드구현할때 맨날 디테일을 깜빡하는걸까

 

import sys
import heapq
t=int(sys.stdin.readline().rstrip())
for _ in range(t):
    n=int(sys.stdin.readline().rstrip())
    max_h=[]
    min_h=[]
    size=0
    for i in range(n):
        opcode,num=sys.stdin.readline().rstrip().split()
        num=int(num)
        if opcode=='I':
            heapq.heappush(min_h,num)
            heapq.heappush(max_h,-1*num)
            size+=1
        else:
            if size==0:
                min_h=[]
                max_h=[]
                continue
            size-=1
            if num==1:
                heapq.heappop(max_h)
            else:
                heapq.heappop(min_h)
    if size==0:
        print("EMPTY")
    else:
        print(-1*max_h[0],min_h[0])

이렇게 수정했다.

뭐지

 

0이 되는 그순간에 힙을 초기화 해야한다.

import sys
import heapq
t=int(sys.stdin.readline().rstrip())
for _ in range(t):
    n=int(sys.stdin.readline().rstrip())
    max_h=[]
    min_h=[]
    size=0
    for i in range(n):
        opcode,num=sys.stdin.readline().rstrip().split()
        num=int(num)
        if opcode=='I':
            heapq.heappush(min_h,num)
            heapq.heappush(max_h,-1*num)
            size+=1
        else:
            size-=1
            if size<=0:
                min_h=[]
                max_h=[]
                size=0
                continue
            if num==1:
                heapq.heappop(max_h)
            else:
                heapq.heappop(min_h)
    if size==0:
        print("EMPTY")
    else:
        print(-1*max_h[0],min_h[0])

이것도 아니다.

 

도저히 모르겠어서 질문게시판을 좀 뒤져봤더니

반례를 찾았다.

40에 40이 나와야하는데 다르게 나온다

min힙에서 데이터를 삭제하지 않아서 발생한문제다.

 

고민을 좀해봐도 도저히 모르겠어서 gpt한테 접근법을 물어봤다.

하...

생각해보면 간단한건데 왜 생각을 못했을까.

import sys
import heapq
t=int(sys.stdin.readline().rstrip())
for _ in range(t):
    n=int(sys.stdin.readline().rstrip())
    max_h=[]
    min_h=[]
    dic={}
    size=0
    for i in range(n):
        opcode,num=sys.stdin.readline().rstrip().split()
        num=int(num)
        if opcode=='I':
            heapq.heappush(min_h,num)
            heapq.heappush(max_h,num*-1)
            if num in dic:
                dic[num]+=1
            else:
                dic[num]=1
        else:
            if num==1:
                while len(max_h)!=0 and  dic[(max_h[0])*-1]==0:
                    heapq.heappop(max_h)
                if len(max_h)>0:
                    dic[(heapq.heappop(max_h))*-1]-=1
                
            else:
                while len(min_h)!=0 and dic[min_h[0]]==0:
                    heapq.heappop(min_h)
                if len(min_h)>0:
                    dic[heapq.heappop(min_h)]-=1
        
    if len(min_h)<1 or len(max_h)<1:
        print("EMPTY")
    else:
        print(max_h[0]*-1,min_h[0])

이렇게 수정해줬다.

..

import sys
import heapq
t=int(sys.stdin.readline().rstrip())
for _ in range(t):
    n=int(sys.stdin.readline().rstrip())
    max_h=[]
    min_h=[]
    dic={}
    size=0
    for i in range(n):
        opcode,num=sys.stdin.readline().rstrip().split()
        num=int(num)
        if opcode=='I':
            heapq.heappush(min_h,num)
            heapq.heappush(max_h,num*-1)
            if num in dic:
                dic[num]+=1
            else:
                dic[num]=1
        else:
            if num==1:
                while len(max_h)!=0 and  dic[(max_h[0])*-1]==0:
                    heapq.heappop(max_h)
                if len(max_h)>0:
                    dic[(heapq.heappop(max_h))*-1]-=1
                
            else:
                while len(min_h)!=0 and dic[min_h[0]]==0:
                    heapq.heappop(min_h)
                if len(min_h)>0:
                    dic[heapq.heappop(min_h)]-=1
    
    while len(max_h)!=0 and  dic[(max_h[0])*-1]==0:
        heapq.heappop(max_h)
    while len(min_h)!=0 and dic[min_h[0]]==0:
        heapq.heappop(min_h)
    if len(min_h)<1 or len(max_h)<1:
        print("EMPTY")
    else:
        print(max_h[0]*-1,min_h[0])

코드 마지막에 값이 유효한지 확인하는 코드를 추가했다.

진짜 헷갈린다.