[백준(BOJ)] #1655- 가운데를 말해요 (파이썬, PyPy3)

문제

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

---

문제 풀이

우선순위 큐 사용

2022.07.19 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 우선순위 큐(Priority Queue), 힙(Heap)

[파이썬으로 배우는 자료구조] 우선순위 큐(Priority Queue), 힙(Heap)

최대힙과 최소힙의 개념 사용

1) 최대힙과 최소힙의 길이가 같으면 최대힙에 값을 저장하고, 길이가 다르면 최소힙에 값 저장

2) 최대힙에서 가장 큰 값이 최소힙에서 가장 작은 값보다 크면 데이터 교환(최대힙에서 가장 큰 값을 기준으로 나누기 위함)

3) 최대힙에서 가장 큰 값이 가운데 값이 됨

 

위와 같이 최대힙과 최소힙이 있다고 가정하고, 입력으로 주어진 1, 5, 2, 10, -99, 7, 5를 처리하는 과정을 그리겠습니다. 실제로 힙은 트리 구조로 이루어져 있지만 그림에서는 우선순위대로 데이터가 저장된다고 가정하겠습니다.

 

1) 최대힙과 최소힙의 길이가 같으므로 최대힙에 1을 저장합니다. 이때 최대힙에서 가장 큰 값은 1이므로 가운데 값은 1입니다.

 

2) 최대힙과 최소힙의 길이가 다르므로 최소힙에 5를 저장합니다. 이때 최대힙에서 가장 큰 값이 1이고, 최소힙에서 가장 작은 값이 5로 기준을 만족하므로 데이터 교환을 하지 않습니다. 최대힙에서 가장 큰 값은 1이므로 가운데 값은 1입니다.

 

3) 최대힙과 최소힙의 길이가 같으므로 최대힙에 2를 저장합니다. 이때 최대힙에서 가장 큰 값이 2이고, 최소힙에서 가장 작은 값이 5로 기준을 만족하므로 데이터 교환을 하지 않습니다. 최대힙에서 가장 큰 값은 2이므로 가운데 값은 2입니다.

 

4) 최대힙과 최소힙의 길이가 다르므로 최소힙에 10을 저장합니다. 이때 최대힙에서 가장 큰 값이 2이고, 최소힙에서 가장 작은 값이 5로 기준을 만족하므로 데이터 교환을 하지 않습니다. 최대힙에서 가장 큰 값은 2이므로 가운데 값은 2입니다.

 

5) 최대힙과 최소힙의 길이가 같으므로 최대힙에 -99를 저장합니다. 이때 최대힙에서 가장 큰 값이 2이고, 최소힙에서 가장 작은 값이 5로 기준을 만족하므로 데이터 교환을 하지 않습니다. 최대힙에서 가장 큰 값은 2이므로 가운데 값은 2입니다.

 

6) 최대힙과 최소힙의 길이가 다르므로 최소힙에 7을 저장합니다. 이때 최대힙에서 가장 큰 값이 2이고, 최소힙에서 가장 작은 값이 5로 기준을 만족하므로 데이터 교환을 하지 않습니다. 최대힙에서 가장 큰 값은 2이므로 가운데 값은 2입니다.

 

7) 최대힙과 최소힙의 길이가 같으므로 최대힙에 5를 저장합니다. 이때 최대힙에서 가장 큰 값이 5이고, 최소힙에서 가장 작은 값이 5로 기준을 만족하므로 데이터 교환을 하지 않습니다. 최대힙에서 가장 큰 값은 5이므로 가운데 값은 5입니다.

 

가운데 값) 1 1 2 2 2 2 5 

 

---

구현

코드

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

if __name__ == "__main__":
    n = int(input())
    lq = list()
    rq = list()
    for _ in range(n):
        t = int(input())
        if len(lq) == len(rq):
            hq.heappush(lq, -t)
        else:
            hq.heappush(rq, t)

        if lq and rq and -lq[0] > rq[0]:
            t1 = hq.heappop(lq)
            t2 = hq.heappop(rq)

            hq.heappush(lq, -t2)
            hq.heappush(rq, -t1)

        print(-lq[0])

결과