[복기] 1655번: 가운데를 말해요

문제

백준 1655번: 가운데를 말해요

알고리즘 분류

• 자료구조
• 우선순위 큐

풀이과정

못 풀어서 솔루션을 봤다. 우선순위큐를 이런 식으로 쓸 수 있다는게 좀 신기했던 솔루션이다. 우선 우선순위큐를 2개 만든다. leftheap과 rightheap. 간단히 말해서, leftheap은 중간값보다 작거나 같은 값을 저장하는 Max Heap이고, rightheap은 중간값보다 큰 값을 저장하는 Min Heap이다. leftheap의 root는 항상 중간값이다. 중간값의 위치는 중간이어야 하므로, leftheap과 rightheap의 길이는 같거나 1이 작다. 로직은 이해해서 직접 구현한 힙으로 로직을 구성했는데, 시간초과가 떴다. 불필요한 연산이 있던건가. 그냥 포기하고 heapq 모듈을 사용했다.

나의 풀이 1: 최대힙 구현(시간초과)

로직은 맞을텐데 시간초과가 뜬다. 힙을 구현해서 통과할 수 있는 문제가 아닌 듯하다.

코드

class Heapq:
    def __init__(self, n):
        self.heapq = [None] + [0] * n
        self.length = 0

    def print(self):
        print(self.heapq[1:self.length+1])

    def heapify(self, left, right):
        parent = left
        temp = self.heapq[parent]

        while parent < right//2+1:
            cl = parent*2
            cr = cl+1
            child = cr if cr <= right and self.heapq[cr] < self.heapq[cl] else cl
            if temp <= self.heapq[child]:
                break
            self.heapq[parent] = self.heapq[child]
            parent = child
        self.heapq[parent] = temp

    def heappush(self, item):
        self.length += 1
        self.heapq[self.length] = item

        child = self.length
        temp = self.heapq[child]

        while child//2 > 0:
            parent = child // 2
            if temp >= self.heapq[parent]:
                break
            self.heapq[child] = self.heapq[parent]
            child = parent
        self.heapq[child] = temp

    def heappop(self):
        if self.length == 0:
            return 0
        root = self.heapq[1]

        self.heapq[1] = self.heapq[self.length]
        self.length -= 1
        if self.length > 0:
            self.heapify(1, self.length)
        return root

    def heaproot(self):
        return self.heapq[1]


import sys
input = sys.stdin.readline
answer = []
n = int(input())
leftheap = Heapq(100000)
rightheap = Heapq(100000)
for _ in range(n):
    x = int(input())
    if leftheap.length == rightheap.length:
        leftheap.heappush(-x)
    else:
        rightheap.heappush(x)

    if rightheap.length > 0 and -leftheap.heaproot() > rightheap.heaproot():
        minVal = rightheap.heappop()
        maxVal = -leftheap.heappop()
        leftheap.heappush(-minVal)
        rightheap.heappush(maxVal)

    answer.append(-leftheap.heaproot())

for i in answer:
    print(i)

나의 풀이 2: heapq 모듈(성공)

문제 풀이에 대한 로직은 위와 동일하다.

코드

import heapq as hq
import sys
input = sys.stdin.readline

n = int(input())

answer = []
leftheap = []
rightheap = []
for _ in range(n):
    x = int(input())

    if len(leftheap) == len(rightheap):
        hq.heappush(leftheap, -x)
    else:
        hq.heappush(rightheap, x)

    if rightheap and -leftheap[0] > rightheap[0]:
        minVal = hq.heappop(rightheap)
        maxVal = -hq.heappop(leftheap)
        hq.heappush(leftheap, -minVal)
        hq.heappush(rightheap, maxVal)

    answer.append(-leftheap[0])

for i in answer:
    print(i)