문제
https://www.acmicpc.net/problem/1655
1655번: 가운데를 말해요
첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1
www.acmicpc.net

문제 풀이
우선순위 큐 사용
2022.07.19 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 우선순위 큐(Priority Queue), 힙(Heap)
[파이썬으로 배우는 자료구조] 우선순위 큐(Priority Queue), 힙(Heap)
우선순위 큐(Priority Queue)란? 일반적인 큐(Queue) 자료구조는 FIFO 구조라는 것을 배웠습니다. 큐 배우기 --> 2022.06.29 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue) [파이썬으로..
c4u-rdav.tistory.com
최대힙과 최소힙의 개념 사용
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])
결과

'PS > 백준' 카테고리의 다른 글
[백준(BOJ)] #1103- 게임 (파이썬, PyPy3) (0) | 2022.11.02 |
---|---|
[백준(BOJ)] #1194- 달이 차오른다, 가자. (파이썬, PyPy3) (2) | 2022.10.30 |
[백준(BOJ)] #1300- K번째 수 (파이썬, PyPy3) (0) | 2022.10.19 |
[백준(BOJ)] #2436- 공약수 (파이썬, PyPy3) (0) | 2022.10.14 |
[백준(BOJ)] #1725- 히스토그램 (파이썬, PyPy3) (0) | 2022.10.13 |