1655번: 가운데를 말해요

1655번: 가운데를 말해요

Explanation:

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

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

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

Algorithm:

Heap Sort

처음에는 힙 정렬을 사용하여 문제를 풀었는데, 시간 초과가 났다. TC에 대해서 생각하고 풀어야하는데 가끔 무지성으로 풀어버린다.. 반성하자 !

import heapq
import sys
input = sys.stdin.readline
T = int(input())
heap = []


def heap_sort(num):
    heapq.heappush(heap, num)
    sorted_nums = []
    copy_heap = heap[:]
    while copy_heap:
        sorted_nums.append(heapq.heappop(copy_heap))
    if len(sorted_nums) % 2 == 0:
        return sorted_nums[(len(sorted_nums)//2)-1]
    else:
        return sorted_nums[len(sorted_nums)//2]


for i in range(1, T+1):
    n = int(input())
    print(heap_sort(n))

Priority Queue

우선순위 큐를 활용하여 최소 힙, 최대 힙 두 개를 만들었다. 양 쪽을 균형있게 채워넣으면서 if (left_heap and right_heap) 두 개의 힙이 비어있지 않고 right_heap[0] < -left_heap[0] 일 때, 각 힙의 값을 바꿔준다.

위와 같이, 바꿔주는 이유는 두 큐를 매번 비교해서 중간 값을 반환하지 않고 하나의 큐를 기준으로 매번 중간 값을 반환하기 위해서 거쳐야 하는 과정이다.

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])

Time Complexity:

python3에 주어진 시간은 0.6초이며, 대략 12 * 10^6의 연산을 허용한다. n의 상한은 10^5, heap sort를 활용한 방법은 10^5 * Log 10^5이기 때문에 통과할 수 없다. 삽입/삭제 연산 O(logN)인 Priority Queue를 사용하여 문제를 해결하였다.