문제 이해
정수를 하나씩 입력받을 때마다 지금까지 외친 수 중에서 중간값을 말해야 한다.
핵심 - 만약 외친 수의 개수가 짝수라면 중간에 있는 두 수 중에서 작은 수를 출력한다!
힙 관련한 섹션에서 문제를 찾아서 풀고 있어서 힙관련 문제임을 인지하고 있었음에도 어떻게 접근해야하는지 잘 감이 오지 않았다.
최대힙이든 최소힙이든 어처피 다 끝값을 구하는데에 최적화 되어있는게 아닌가? 중간값을 뽑아야하는데, 힙을 쓴다고?
결국 힌트를 찾아봤고, 좀 다듬어 보았다
접근 방식
방금 언급한 것처럼 HEAP을 써야하는데, 파이썬에서는 heapq 모듈을 사용하여 우선순위 큐를 쉽게 구현할 수 있다.
힌트
처음에는 하나의 힙을 구현할 생각만했는데, 두개의 힙을 활용한다는 생각까지 닿지 못해서 오래 걸렸던 것 같다. 결국 그 부분에서 힌트를 얻었다.
대략적인 풀이 구조
아까 언급한 대로 최대힙과 최소힙 두개를 만들어서 반반으로 나눠주고, 최대힙의 최대값, 최소힙의 최소값이 결국 중간값일 것이다.
- 최대 힙(maxheap): 입력된 수 중 작은 값들을 저장
- 최소 힙(minheap): 입력된 수 중 큰 값들을 저장
입력되는 수를 번갈아가며 최대 힙과 최소 힙에 넣어주면 자연스럽게 반으로 나뉠 것이다. 숫자를 maxheap먼저 넣어주게되면 항상 maxheap의 루트를 중간값, 중간중에 작은값으로 유지시켜줄 수 있을 것이다.
항상 최대 힙의 크기가 최소 힙의 크기보다 크거나 같도록 유지합니다. 이렇게 하면 최대 힙의 최상단 값이 항상 중간값 또는 중간값 중 작은 값이 됩니다.
문제 해결 과정
짝수 번째 입력되는 수는 최대 힙에 추가합니다. 이때, 값의 부호를 반대로 바꾸어 넣습니다.
홀수 번째 입력되는 수는 최소 힙에 추가합니다.
최대힙 구현 - heapq 모듈은 최소 힙만 지원하기 때문에, 최대 힙처럼 동작하게 하려면 음수로 변경해서 넣어준뒤, 뺄 때 음수로 빼주면 됩니다!
- 최소 힙이 비어있지 않고, 최대 힙의 루트(최상단)이 (부호를 바꾼 상태)이 최소 힙의 최상단 값보다 크다면, 두 값을 교환
만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. 이 이유 때문에 둘이 변경해주는 것이다!
- 최대 힙의 루트를 항상 출력해주면 됩니다. 중간값 혹은 중간값 중 작은 값으로 세팅을 해놨기 때문!
주의 사항: 값의 부호를 다시 바꿔야 원래의 값을 얻을 수 있습니다.
풀이 코드
import sys
import heapq
n = int(sys.stdin.readline().strip())
maxheap = []
minheap = []
arr = [int(sys.stdin.readline().strip()) for _ in range(n)]
for (i,element) in enumerate(arr):
if(i%2 ==0 ): #짝수 짝수면 maxHeap에 넣어줘야함
heapq.heappush(maxheap,-element)
else:
heapq.heappush(minheap,element) #홀수면 minHeap에 넣어주자
if( minheap and (-maxheap[0] > minheap[0])):
#이게 maxheap의 최대가 Min의 최소값보다 크면? 짝수면 작은수를 말해야하니까 변경해주기
#처음에 maxheap부터 들어가니까 if(minheap)으로 예외처리
max_value = -heapq.heappop(maxheap) #최대힙에서 루트빼주기
min_value = heapq.heappop(minheap) #최소힙에서 루트빼주기
heapq.heappush(minheap,max_value)
heapq.heappush(maxheap,-min_value)
#최대힙의 루트와 최소힙의 루트를 비교해서 최소가 더 크면 자리 바꿔주기
# -> "짝수개라면 중간에 있는 두수 중에서 작은 수를 말해야한다" 때문
print(-maxheap[0]) #최대힙이므로 음수붙여서 출력
시간 복잡도
힙 연산 = O(log N) , 입력되는 수의 개수를 N
전체 시간 복잡도 -> O(N log N)
후기
이제 힙을 제대로 푼게 얼마 안되지만 지금까지 느낀점은 일단 얕은 단계의 문제에서는 heap이 최대힙, 최소힙인만큼 어떻게 최소값, 최대값을 사용해줄 수 있을지를 좀 고민해보면 도움이 될 것 같다는 생각이 들었다.
👍👍👍