가운데를 말해요 - 1655번
문제
백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.
예를 들어 백준이가 동생에게 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줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.
풀이
1. 반복문 사용 - 시간초과
import sys
import heapq
input = sys.stdin.readline
N = int(input())
heap = []
for _ in range(N):
heapq.heappush(heap, int(input()))
tli = []
for _ in range((len(heap)-1)//2):
t = heapq.heappop(heap)
tli.append(t)
l = heapq.heappop(heap)
print( l )
for tl in tli:
heapq.heappush(heap, tl)
heapq.heappush(heap, l)문제 중 "지금까지 백준이가 말한 수 중에서 중간값"의 중간값이란 인덱스가 중간이라는 뜻이다.
동기 신승훈이랑 같이 했는데 어쩐지 이야기하면서 하니까 코드가 더 잘 짜지는 기분이 들었다... 위 반복문으로 접근하고서 시간초과 오답처리를 당했다. 승훈이의 스포를 통해 예언된 결과였다 ㅋㅋ
입력값을 하나 받을 때, 받고 나서 반복문으로 통해 "현재 heap 길이 - 1"의 반만큼(//2) heapq.heappop()해준 뒤 이어서 그 다음 heapq.heappop()하는 것은 print한다.
모든 heapq.heappop()했던 요소들은 버려지지 않게 임시저정함 변수 tli에 담아놨다가 다시 반복문을 통해 heapq.heappush()해줘 기존의 heap을 유지되게끔 한다.
- 여기서! 팝하는 반복문의 range가 (현재 heap 길이 - 1)//2 인 이유: 이 반복문은 현재 heap 길이의 절반을 다 팝하는 것이 아니라, 중간 직전까지만 팝하는 반복문이다. 예를 들어 현재 heap의 길이가 5라고 하면 인덱스 3의 요소를 놔두고, 6이라고 하면 인덱스 3(과 4)의 요소를 놔두고 그 전까지만 반복문으로 팝해줄 것이란 말이다.
- 여기서! "누적된 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수 리턴"에 대한 구문이 없는 이유: 파이썬 default의 heap 형태인 min heap의 특성상, 중간에 남은 두 수 중 무조건 작은 수가 먼저 팝되기 때문!
어쨌든 이 풀이는 시간초과가 된다.
입력값을 저장하는 이터러블을 하나가 아닌 두 가지로 나누어 반복문 사용을 지양해야 하고, 애당초에 리스트 대신 다른 자료구조를 써야 한다.
그래서 우리는 입력값을 이분할 힙을 각각 만들 거다. 둘 중 하나의 힙의 루트값이 언제나 중간값이 되도록 고루 이분하는 것이다.
2. max heap과 min heap을 선언하여 각각 mid값 위와 아래로 이분
아래의 블로그가 잘 설명되어 있어서 도움을 많이 받았다.
https://velog.io/@uoayop/BOJ-1655-%EA%B0%80%EC%9A%B4%EB%8D%B0%EB%A5%BC-%EB%A7%90%ED%95%B4%EC%9A%94Python
아래의 코드는 정답이다.
import sys
import heapq
input = sys.stdin.readline
N = int(input())
max_h, min_h = [], []
for i in range(N):
num = int(input())
if len(max_h) == len(min_h):
heapq.heappush(max_h, -num)
else:
heapq.heappush(min_h, num)
if len(max_h)>=1 and len(min_h)>=1 and max_h[0]*-1>min_h[0]:
tar_max_value = heapq.heappop(max_h) * -1
tar_min_value = heapq.heappop(min_h)
heapq.heappush(max_h, tar_min_value * -1)
heapq.heappush(min_h, tar_max_value)
print(max_h[0] * -1)풀이를 설명하겠다.
이 풀이는 역시 입력값을 하나 받을 때마다 heap에 푸시해주고 있는데,
- 우선 입력이 홀수번째이면 min_h힙에, 입력이 짝수번째라면 max_h힙에 넣는다.
(온라인 상에서 많은 사람들이 max_h과 min_h이라는 작명 대신 left_h과 right_h을 쓰기도 했다. 이분탐색에서 left와 right 방식의 변수 작명을 맘에 안 들어했는데 이 문제의 경우는 합당해보인다...)
max_h 또는 left_h은 max heap으로 설정해줄 것이다. max heap은 넣을 때 입력값에 마이너스, 팝할 때 입력값에 마이너스를 붙이면 성립한다.
- 우리는 왼쪽 힙을 최대 힙으로 정렬하고, 오른쪽 힙을 최소 힙으로 정렬할 것이다. 그렇게 되면 양쪽 힙의 루트들은 절대값으로 따졌을 때 언제나 전체 입력값의 중간이 된다.
--> 그 중 우리는 max heap과 min heap의 성질을 이용해 언제나 max heap의 루트가 우리가 목표로 하는 "짝수번 입력됐을 시 중간 두 개 중 더 큰" 값이 되는 거다.
맥스힙의 첫번째 요소는 맥스힙에서 가장 큰 값이다.
마찬가지로 민힙의 첫번째 요소는 민힙에서 가장 작은 값이다.다시 말해 왼쪽 힙(맥스힙)의 첫번째 요소는 항상 중앙값이 되는 것이고,
이를 이용해 우리는 언제나 max_h 혹은 left_h의 pop값을 print하면 되게끔 식을 짜는 게 목표인 거다.
그리고 또 하나 중요한 부분이 있다.
고로 우리가 1번과 같은 기계적인 "홀수번째==max힙으로! 짝수번째==min힙으로!"를 수행하다 보면, 현재 입력값이 max min 개념에 걸맞지 않게 잘못 들어가는 경우도 생길 것이다.
입력값이 잘못된 힙에 들어갔을 시의 상태는 아마도 다음과 같을 것이다:
- a. 양쪽 힙 모두 요소가 하나 이상씩 있어 비교가 가능한 시점이어야 한다.
- b. 맥스힙의 루트(최대값)(입력값 중 중간)가 중간 값이어야 하는데, 말인즉 맥스힙의 모든 요소가 민힙의 모든 요소보다 커야 한다.
그러므로 만약 민힙의 루트(최하값)(입력값 중 중간+1, 입력값 길이가 짝수일 땐 중간 두 개 중 큰 거)가 맥스힙의 루트(입력값 중 중간, 입력값 길이가 짝수일 땐 중간 두 개 중 작은 거)보다 크면, 그건 해당 값이 잘못된 힙에 입력값으로 들어간 상태일 테다.
그래서, 우린
if len(max_h)>=1 and len(min_h)>=1 and max_h[0]*-1>min_h[0]:의 조건문으로 입력값이 잘못된 힙에 들어간 경우를 바로바로 방어한다.
이렇게 되면 우린 언제나 max_h의 루트값을 print하면 된다.
