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

문제 보기

이 문제는 이진 탐색 혹은 우선순위 큐 문제이다.

 

수빈이가 외치는 수가 주어졌을 때, 현재까지 입력받은 숫자의 중간값을 계속해서 출력하면 된다.

중간값을 출력하기 위해서는 정렬이 필요하다고 생각하였다. 하지만 숫자를 입력받을 때마다 정렬하면 시간 초과가 발생할 것 같았다.

따라서 수빈이가 외치는 수가 들어오면 이진 탐색을 통해 해당 숫자가 삽입될 위치를 찾고 삽입하는 방식으로 시간을 단축하였다.

 

알고리즘 동작은 아래와 같다.

1. 숫자를 입력받는다.

2. 이진 탐색을 활용하여 해당 숫자가 삽입될 위치를 찾는다.

3. 숫자를 삽입한다.

4. 현재까지 입력된 숫자의 개수가 짝수인지 홀수인지 파악하고 올바른 위치의 값을 출력한다.

코드

from bisect import bisect_left

if __name__ == "__main__":
    n = int(input())  # 수빈이가 외치는 정수의 개수 입력받기
    array = []  # 입력받은 숫자를 저장할 리스트 선언

    # 첫 번째 숫자 입력받기
    num = int(input())
    array.append(num)
    print(num)

    # array 현재 길이
    length = 1

    # 두 번째 숫자부터 차례대로 입력받기
    for _ in range(n - 1):
        num = int(input())
        # 숫자가 삽입 될 인덱스 찾기
        index = bisect_left(array, num)
        # 숫자 삽입, array 길이 1 증가
        array.insert(index, num)
        length += 1

        if length % 2 == 0:  # 짝수개
            print(min(array[length // 2 - 1], array[length // 2]))
        else:
            print(array[length // 2])