📌 문제
백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.
예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.
📌 입력
첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.
📌 출력
한 줄에 하나씩 N줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.
📌 문제 풀이
👨🏫 접근
힙을 사용해서 푸는 문제. 이미 우선순위 큐를 사용해서 풀어야 하는 문제라고 해서 접근할 수 있었는데, 몰랐으면 접근이 굉장히 어려웠을 것 같다. 우선순위 큐로 작은 수와 큰 수로 나누어서 문제를 풀이해준다. 그리고, 짝수에서는 더 작은 것을 출력할 수 있기 때문에 작은 수를 담는 리스트에서 계속해서 수를 뽑아내도록 한다.
작은 수를 담는 배열은 최대 힙을 사용하고, 큰 수를 담는 배열은 최소 힙을 사용하도록 한다. 작은 수들을 담은 리스트에서는 가장 큰 값을 출력해야 가운데에 가까워지기 때문이다. 비슷한 이유로 큰 수를 담는 배열은 가장 작은 갑을 출력해야 가운데에 가까워진다.
👨🏫 문제 풀이
📄 전체 코드
import sys
import heapq
input = sys.stdin.readline
n = int(input())
left, right = [], []
for _ in range(n):
k = int(input())
if len(left) == len(right):
heapq.heappush(left, (-k, k)) # 좌측은 최대 힙이 필요
else:
heapq.heappush(right, (k, k)) # 우측은 최소 힙이 필요, 간단한 출력을 위해 입력 양식 통일
if right and left[0][1] > right[0][1]:
MIN = heapq.heappop(right)[1]
MAX = heapq.heappop(left)[1]
heapq.heappush(left, (-MIN, MIN))
heapq.heappush(right, (MAX, MAX))
print(left[0][1])
📄 준비
import sys
import heapq
input = sys.stdin.readline
n = int(input())
left, right = [], []
좌측과 우측으로 두 개의 배열을 만들어주었다. 이렇게 해서 조건에 따라서 좌 우로 값을 분류한다.
📄 풀이
for _ in range(n):
k = int(input())
if len(left) == len(right):
heapq.heappush(left, (-k, k)) # 좌측은 최대 힙이 필요
else:
heapq.heappush(right, (k, k)) # 우측은 최소 힙이 필요, 간단한 출력을 위해 입력 양식 통일
if right and left[0][1] > right[0][1]:
MIN = heapq.heappop(right)[1]
MAX = heapq.heappop(left)[1]
heapq.heappush(left, (-MIN, MIN))
heapq.heappush(right, (MAX, MAX))
print(left[0][1])
두 개의 길이가 같은 상황에서는 왼쪽에 값을 보낸다. 그 이유는 우리는 항상 좌측에서 값을 뽑아낼 것이기 때문이다. 만약 짝수일 때 더 큰 값을 출력하라고 했으면, 오른쪽에 값을 보냈을 것이다.
그 후에 만약 좌측에서 가장 큰 값이 우측에서 가장 작은 값보다 크다면 그 값은 가운데 값이 아니라 더 큰 값이다. 그렇기 때문에 서로 값을 스와이프 해준다. 힙으로 매번 값을 넣었기 때문에 0번 인덱스를 사용하면 가장 큰 값이나 가장 작은 값을 얻어낼 수 있다.
📌 총평
힙 문제는 쉬운 문제들이었는데 확실히 자료구조를 생각해내서 문제를 풀라고 하니까 난이도가 급상승한다...
'Algorithm > Data Structure' 카테고리의 다른 글
[Python - Data Structure, Union Find] 1976 여행 가자 (0) | 2022.09.17 |
---|---|
[Python - Data Structure, Map] 4195 - 친구 네트워크 (0) | 2022.09.16 |
[Python - Data Structure, Union Find] 1717 집합의 표현 (0) | 2022.09.16 |
[Python - heapq] 11286 절댓값 힙 (0) | 2022.09.05 |
[Python - Stack] 1874 스택 수열 (0) | 2022.07.26 |