문제
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.1 초 (하단 참고) | 128 MB | 64554 | 18967 | 14190 | 30.382% |
문제 설명
백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.
예를 들어 백준이가 동생에게 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
7
1
5
2
10
-99
7
5예제 출력 1
1
1
2
2
2
2
5내 풀이
초기 나의 아이디어는 최소힙을 구현한 heapq 모듈을 통해 len(num)//2만큼 pop을 하면 되나?라고 생각했지만 시간제한이 무려 0.1초인 이 문제에서 nlogn 의 시간복잡도로는 해결이 어려울 것 같았다.
그래서 찾아본 풀이는 힙을 각각 두개 만드는 것!
-> 왼쪽 힙은 최대힙, 오른쪽 힙은 최소 힙으로 만들어서 값 비교를 통해 양쪽 힙에 새로운 값을 넣어주는 것
-> 출력되는 중앙값은 항상 왼쪽 힙의 root값일 것이다.
이 블로그분이 이해하기 쉽게 문제의 조건을 작성해주셨다.
- 왼쪽 힙과 오른쪽 힙의 길이가 같으면 (요소 * -1) 을 왼쪽 힙에 삽입한다.
1-1. 그렇지 않으면 오른쪽 힙에 삽입한다.- 왼쪽 힙과 오른쪽 힙에 요소가 존재하고, 왼쪽 힙의 (첫번째 요소* -1) 가 오른쪽 첫번째 요소보다 클 때
2-1. 왼쪽 힙의 첫번째 요소와 오른쪽 힙의 첫번째 요소를 바꿔준다. ( -1을 곱해준 뒤 바꿔준다. )- 왼쪽 힙의 (첫번째 요소 * -1)를 출력한다.
위 조건을 참고해 작성한 코드는 아래와 같다.
import sys
input = sys.stdin.readline
import heapq as h
n = int(input())
max_heap = []
min_heap = []
for _ in range(n):
num = int(input())
if len(max_heap) == len(min_heap):
h.heappush(max_heap, -1 * num)
else:
h.heappush(min_heap, num)
if max_heap and min_heap and max_heap[0] * -1 > min_heap[0]: # 만약 왼쪽 힙의 최댓값이 오른쪽 힙의 최솟값보다 클 경우
h.heappush(max_heap, min_heap.pop() * -1)
h.heappush(min_heap, max_heap.pop() * -1)
print(max_heap[0] * -1)
내가 틀린 이유를 복기해보자.
1) 시간제한이 0.1초인 이 문제에서 input에서 sys.stdin.readline을 사용하지 않을 수 없다. input()을 그대로 사용하면 당연히 시간초과.
2) 언어를 C++로 제출했다; <- 걍 바보임
번외)
h.heappush(max_heap, min_heap.pop() * -1)
h.heappush(min_heap, max_heap.pop() * -1)이 문제에서는 이렇게 구현해도 문제가 없다.
코드도 간결하고 시간도 더 짧게 걸린다.
min_value = h.heappop(min_heap)
max_value = h.heappop(max_heap)
h.heappush(max_heap, min_value * -1)
h.heappush(min_heap, max_value * -1)하지만 앞으로는 이렇게 구현하는 것이 더 일관적이고 명료한 코드를 작성하는데 좋을 것 같다,, 값 변경의 우려가 없음.
시간제한이 걸린 우선순위큐 문제는 파이썬의 heapq 모듈을 사용해야 효과적이라는 사실
파이썬의 다양한 라이브러리와 모듈을 많이 활용해보자
