[boj] 1655번: 가운데를 말해요

출처 : https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

 

 

1. 문제 설명 

백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간 값을 말해야 한다. 만약 외친 수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말한다.

1을 외치면 지금까지 `백준이가 외친 수 = [1]이므로 1
5를 외치면 `백준이가 외친 수 = [1,5], 두 수중 작은 수는 1
2를 외치면 `백준이가 외친 수 = [1,5,2] 중간 수는 2

위와 같은 방식으로 수를 구해야 한다.

 

 

 

2. 접근 방식

처음에는 힙 정렬을 사용하여 문제를 풀었는데, 시간 초과가 났다. TC에 대해서 생각하고 풀어야하는데 가끔 무지성으로 풀어버린다.. 우선순위 큐를 활용하여 최소 힙, 최대 힙 두 개를 만들었다. 양 쪽을 균형있게 채워넣으면서 if (left_heap and right_heap) 두 개의 힙이 비어있지 않고 right_heap[0] < -left_heap[0] 일 때, 각 힙의 값을 바꿔준다. 위와 같이, 바꿔주는 이유는 두 큐를 매번 비교해서 중간 값을 반환하지 않고 하나의 큐를 기준으로 매번 중간 값을 반환하기 위해서 거쳐야 하는 과정이다.

 

 

 

3. 주석 달기 (변수 설명, 각 줄마다 문장으로 설명, 함수 설명)

import heapq
import sys
input = sys.stdin.readline
T = int(input())
left_heap = []
right_heap = []
for _ in range(T):
    num = int(input())
    if len(left_heap) == len(right_heap):
        heapq.heappush(left_heap, -num)
    else:
        heapq.heappush(right_heap, num)

    if (left_heap and right_heap) and right_heap[0] < -left_heap[0]:
        left_tmp = heapq.heappop(left_heap)
        right_tmp = heapq.heappop(right_heap)
        heapq.heappush(left_heap, -right_tmp)
        heapq.heappush(right_heap, -left_tmp)

    print(-left_heap[0])

 

 

4. 분석

1. Time : python3에 주어진 시간은 0.6초이며, 대략 12 * 10^6의 연산을 허용한다.  n의 상한은 10^5, heap sort를 활용한 방법은 10^5 * Log 10^5이기 때문에 통과할 수 없다. 삽입/삭제 연산 O(logN)인 Priority Queue를 사용하여 문제를 해결하였다. 
2. Space :
3. 소요시간 : 1시간 
4. 제출 횟수 (무작정 제출하기 않기)  : 3회 
5. 어려웠던 부분과 해결한 방법 : 비슷한 유형을 꾸준히 반복적으로 풀고 복습하는 습관을 들여야할 것 같다. 
6. 실수가 줄어들었는가 ?