[python] 백준 - 1655. 가운데를 말해요

🤔문제 해결

• G2 | 우선순위 큐

처음에는 가볍게 정렬로 풀었지만, 시간초과가 발생했다. ( 바이너리서치는 통과 된다고 함 )

가운데 값 구하기를 열심히 찾아봤지만 없었다. 어쩔 수 없다.

 

이 문제의 의도는 우선순위 큐를 활용하는 것이다.

파이썬의 힙큐 모듈을 사용하면 되는데, 최소힙 기준으로 되어있다.

최소힙은 가장 작은 원소가 루트에 위치하는 것이다.

우리는 가운데 값을 찾아야 하기 때문에 힙을 두개 만들어서

왼쪽의 가장 큰 수와 오른쪽의 가장 작은 수를 비교하여 가운데 값을 구할 것이다.

이렇게 두 부분으로 나누면 가운데 값을 구 할 수 있다.

하지만!!!!!!!!!!! 최소힙으로 힙큐 모듈이 구성되어 있으므로, 왼쪽의 구성은 음수를 붙여서 거꾸로 만들어야한다.

이렇게 하면 왼쪽의 0번과 오른쪽의 0번을 비교할 수 있다. (당연히 꺼낼 때는 -를 다시 붙여준다.)

💻소스 코드

import sys
import heapq

input = sys.stdin.readline


def push_heap(left_heap: list, right_heap: list, num: int, n: int):
    # 숫자의 개수가 홀수이면 오른쪽에 넣고, 짝수면 왼쪽에 넣기
    if n % 2 == 1:
        heapq.heappush(right_heap, num)
    else:
        heapq.heappush(left_heap, -num)


def make_mid_heap(left_heap: list, right_heap: list):
    # 레프트의 최대값이 라이트의 최소값보다 크면 위치 교환
    if left_heap:  # 라이트만 있을 수 있기 때문에 if문 처리
        left_max = -left_heap[0]
        right_min = right_heap[0]
        if left_max > right_min:
            heapq.heappush(left_heap, -heapq.heappop(right_heap))
            heapq.heappush(right_heap, -heapq.heappop(left_heap))


def get_mid_number(left_heap: list, right_heap: list, n: int) -> int:
    # 숫자의 개수가 홀수이면, 라이트에서 최소값을 반환
    # 숫자의 개수가 짝수이면, 레프트 최대와 라이트 최소를 비교하여 최소값 반환
    if n % 2 == 1:
        return right_heap[0]
    else:
        return min(-left_heap[0], right_heap[0])


if __name__ == '__main__':
    N = int(input())  # 숫자의 개수
    left_numbers = []  # 최대 힙(최대값을 음수로 넣어 최대값이 0번에 오게 한다)
    right_numbers = []  # 최소 힙

    for i in range(1, N + 1):
        number = int(input())
        push_heap(left_numbers, right_numbers, number, i)
        make_mid_heap(left_numbers, right_numbers)
        answer = get_mid_number(left_numbers, right_numbers, i)
        print(answer)
 

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

링크: https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요