BOJ 7662 PS일기

요구사항

Dual Priority Queue를 구현하라는 문제이다. 다음의 3가지 명령이 들어온다. 임의의 수를 삽입, 최솟값 삭제, 최댓값 삭제.
위 3가지 명령 조합으로 100만개의 연산을 N * logN의 속도로 해결해야한다.

문제접근

힙을 이용하여 해결하기로 했다. 삽입과 삭제가 트리의 높이만큼 시간이 걸리기에 N * logN의 속도를 가지는 자료구조이다.

데이터 흐름

삽입

내림차순힙과 오름차순 힙을 준비한다. 들어온 입력이 삽입이라면 오름차순 힙에는 그대로 들어가고 내림차순 힙에는 마이너스를 붙여서 넣는다. 이 때 포인트는 이 데이터를 사용했는지 검사를 위해 전역에 boolean리스트에 디폴트값 True를 넣어두고 두 힙에 삽입할 때 데이터와 함께 boolean리스트의 인덱스를 함께 넣어준다.

삭제

기본적으로 파이선의 힙은 min heap으로 소팅된다. 최솟값 삭제 명령이라면 먼저 루트를 pop하고 삽입시 함께 저장했던 인덱스 값을 key로 사용하여 boolean리스트에 접근한다. 사용하지 않은 값이라면 True로 저장되어있으므로 값을 False로 변경 후 삭제 로직을 마무리한다. 만약 최댓값 삭제 명령에서 방금전에 접근했던 값에 접근한다면 이미 최솟값 삭제에서 사용했으므로 다음 최댓값을 찾아 삭제 로직을 반복한다.

import heapq

data = open(0).readlines()
isStart = False #현 시점 삽입 삭제 시작 여부
maxList = [] #내림차순 힙 리스트
minList = [] #오름차순 힙 리스트
realData = [] #데이터 사용여부
realDataIdx = 0 #데이터 사용여부 인덱스(key)

def print_val(maxList, minList):
    big,small = my_pop(maxList), my_pop(minList)
    if big != None:
        big = -big
    if big != None and small == None:
        print(big, big)
    elif big == None and small != None:
        print(small, small)
    elif big == None and small == None:
        print('EMPTY')
    else:
        print(big, small)
        
def my_pop(dataList):
    while dataList:
        data,idx = heapq.heappop(dataList)
        if realData[idx] == False:
            continue
        realData[idx] = False
        return data
    return None
        
for i in data:
    i = i.split(' ')
    if (isStart == True) and (not i[0].isalpha()):
        print_val(maxList, minList)
        maxList.clear()
        minList.clear()
        realData.clear()
        realDataIdx = 0
        isStart = False
        continue
    if not i[0].isalpha():
        continue
    isStart = True
    cmd, data = i[0], int(i[1])
    ## 데이터 삽입 
    if cmd == 'I':
        heapq.heappush(minList, (data, realDataIdx))
        heapq.heappush(maxList, (-data, realDataIdx))
        realData.append(True)
        realDataIdx += 1
        continue
    ## 데이터 삭제
    if not maxList or not minList:
        continue
    # 최솟값 삭제
    if data == -1:
        my_pop(minList)
    else: # 최댓값 삭제
        my_pop(maxList)
print_val(maxList, minList)