[백준/파이썬] 1655 : 가운데를 말해요

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

1655번: 가운데를 말해요

문제 요약 : 정수를 하나씩 외칠 때마다 말한 수 중에 중간값을 말해야한다. 만일 짝수라면 중간에 있는 두 수 중 작은 수를 말한다.

 

 

시도 )

N = int(input())
number = []
for i in range(1,N+1):
    number.append(int(input()))
    number.sort()
    if i % 2 == 0:  # 짝수
        print(min(number[(i//2) - 1], number[i//2]))
    else :  # 홀수
        print(number[i//2])

골드2인데 왜 이렇게 쉽지? 하고 봤더니

시간 제한이 있었다.. 🙄

 

 

풀이 )

우선순위 큐를 이용하는 문제이다.

우선순위 큐에 대한 내용은 요기에..!

 

무작정 number리스트를 힙으로 바꾸어 적용했는데, 우선순위 큐는 완전 정렬이 아닌 느슨한 정렬이기에 중간값을 구하는 데에는 완전 정답까진 아니였다.

즉, 왼쪽힙과 오른쪽힙 두개로 나누어 사용하여야했다.

 

참고로 질문게시판을 보니 이분 탐색으로 푼 분이 계시던데, 재채점에선 시간초과가 떠서 무조건 우선순위큐로 풀어야하는듯 하다.

import heapq
import sys
input = sys.stdin.readline

leftHeap = []   # 최대힙
rightHeap = []  # 최소힙

for i in range(int(input())):
    number = int(input())

    if len(leftHeap) == len(rightHeap) : 
        heapq.heappush(leftHeap, -number)
    else :
        heapq.heappush(rightHeap, number)
        
    
    if rightHeap and (-1 * leftHeap[0]) > rightHeap[0] :
        left = heapq.heappop(leftHeap)
        right = heapq.heappop(rightHeap)

        heapq.heappush(rightHeap, -left)
        heapq.heappush(leftHeap, -right)
    print(leftHeap[0]*-1)

leftHeap은 최대힙, rightHeap은 최소힙으로 구현한다.

leftHeap의 루트노드는 가장 큰 값(음수로 저장), rightHeap의 루트노드는 가장 작은 값이 나오게 된다.

 

만일 left와 right의 길이가 같다면 left에 새로운 값을 넣어주고,

다르다면 right가 더 짧을 것이기 때문에 right에 새로운 값을 넣어준다.

이렇게 하는 이유는 left는 중간값과 같거나 작은 값으로, right는 중간값보다 큰 값으로 유지하기 위함이다.

즉 언제나 left를 꺼내기 위해서 했다고 생각하면 될것같다.

 

left의 루트노드 * -1 한 값과 right의 루트노드를 비교하여 더 작은 값을 left에, 더 큰 값을 right에 넣어준다.

 

left노드의 루트 노드를 *-1 하여 출력해준다.