백준 1655 <가운데를 말해요> Python

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

1655번: 가운데를 말해요

---

수가 들어올 때 마다 정렬이 되어야 한다

그러므로 정렬에 많은 시간이 소요되면 안된다

다른 순서는 필요없고 중간만 맞으면 된다

 

라는 특성이 문제를 푸는데 가장 중요한 포인트였습니다.

우선 힙(우선순위큐)를 사용했는데, 이유는 다음과 같습니다.

 

수가 들어올 때 마다 정렬이 되어야 한다

-> 힙 삽입으로 해결

정렬에 많은 시간이 소요되면 안된다

-> 힙 정렬로 해결

다른 순서는 필요없고 중간만 맞으면 된다

-> 힙은 중간 순서는 맞지 않을 수 있지만 가장 우선순위가 높은 수는 알 수 있다, 힙을 두 개 쓰자

 

결국 속도가 가장 빠르기 때문에 썼습니다.

심지어 최대힙과 최소힙 두 개를 쓰면 최적의 경우 한번에 정렬을 하나의 힙만 해도 되기 때문에 더 빠르다고 볼 수 있습니다.

 

기본 아이디어는 '입력된 수들의 리스트 중 앞 부분 절반은 최대 힙으로, 뒷 부분 절반은 최소 힙으로 생각하고 두 힙을 합치면 다른 순서는 몰라도 가운데는 항상 찾을 수 있다는 것' 입니다.

---

# 힙 사용

import heapq

# 편하게 하려고 deque 사용

from collections import deque

import sys

def solution(N, num_list):

    # 최대 힙

    max_heap = []

    # 최소 힙

    min_heap = []

    # deque, popleft 쓰려고..

    num_list = deque(num_list)

   

    i = 0

    while True:

        # 모두 넣으면 끝

        if not num_list:

            break

        # 홀수일 때는 max heap 에

        # max heap 이라 - 붙여서 입력

        if not i%2:

            heapq.heappush(max_heap, -num_list.popleft())

        # 짝수일 때는 min heap 에 번갈아서 넣어줌

        else:

            heapq.heappush(min_heap, num_list.popleft())

        # max heap 의 최댓값과 min heap 의 최솟값을 비교해서 교환

        # max heap 과 교환이라 - 붙여서 비교, 교환

        if i and -max_heap[0] > min_heap[0]:

            max_pop = -heapq.heappop(max_heap)

            min_pop = heapq.heappop(min_heap)

           

            heapq.heappush(max_heap, -min_pop)

            heapq.heappush(min_heap, max_pop)

           

        # i 증가

        i += 1

        # 출력

        # max heap 이라 - 붙여서 출력

        print(-max_heap[0])

           

N = int(sys.stdin.readline())

num_list = [int(sys.stdin.readline()) for _ in range(N)]

solution(N, num_list)