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

이또삐(이민혁)·2023년 4월 19일

baekjoon

CODINGTEST

목록 보기

54/96

성능 요약

메모리: 130680 KB, 시간: 472 ms

분류

자료 구조, 우선순위 큐

문제 설명

백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

출력

한 줄에 하나씩 N줄에 걸쳐 백준이의 동생이 말해야 하는 수를 순서대로 출력한다.

아이디어, 문제풀이

알고리즘 구조!
1. 왼쪽 힙과 오른쪽 힙의 길이가 같으면 (요소 * -1) 을 왼쪽 힙에 삽입한다.1-1. 그렇지 않으면 오른쪽 힙에 삽입한다.
2. 왼쪽 힙과 오른쪽 힙에 요소가 존재하고, 왼쪽 힙의 (첫번째 요소* -1) 가 오른쪽 첫번째 요소보다 클 때2-1. 왼쪽 힙의 첫번째 요소와 오른쪽 힙의 첫번째 요소를 바꿔준다. ( -1을 곱해준 뒤 바꿔준다. )
3. 왼쪽 힙의 (첫번째 요소 * -1)를 출력한다.
왼쪽 오른쪽을 나눠서 저장해야 시간복잡도를 만족할수 있다. 단순히 넣고 정렬한뒤 뽑아내려고 하면 O(nlogn)이 되어 초과된다.

TROUBLE SHOOTING

이런 문제들은 어떻게 접근해야 할지 아직은 잘 모르겠다. 일단 문제를 읽고, 내가 원하는 방식대로 코드를 작성하면, 구현이 가능하다. 그랬을때의 문제점은 항상 시간복잡도에서 오는데, 이 문제를 우선순위큐로 풀어야하는 이유가 되고, 더 나아가서 두개의 힙을 만들어 서로 길이비교를 하며 차례대로 넣는 개념까지 필요하다.
이런 개념 자체는 읽자마자 한번에 이해가 되긴 하지만, 만약 이 문제를 블라인드 테스트로 풀어야 한다면? 하는 생각들이 요즘들어 가장 많이 드는 생각 들이다. 보고 이해하는게 중요한걸까? 아니면 혼자 어떻게든 해결하는게 맞는걸까… 아직은 확신이 없다.
문제 풀이 자체는 앞선 우선순위큐 문제인 “최대 힙”의 heapq 모듈 사용법을 통해 간단하게 구현할 수 있다.

코드

#https://www.acmicpc.net/problem/1655
#가운데를 말해요
#1655

import heapq
import sys
input =sys.stdin.readline

n = int(input())

left_heap = []
right_heap = []

for i in range(n):
    a = int(input().strip())

    if len(left_heap) == len(right_heap):
        heapq.heappush(left_heap, -a)
    else:
        heapq.heappush(right_heap, a)

    if right_heap and -left_heap[0] > right_heap[0]:
        max_left = -heapq.heappop(left_heap)
        min_right = heapq.heappop(right_heap)

        heapq.heappush(left_heap, -min_right)
        heapq.heappush(right_heap, max_left)

    print(-left_heap[0])

참고 코드

import sys
import heapq

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

leftheap = []
rightheap = []

for _ in range(n):

    # 현재 숫자
    num = int(sys.stdin.readline())

    # leftheap의 길이가 rightheap의 길이와 같다면
    if (len(leftheap) == len(rightheap)):
        # leftheap에 현재 숫자를 음수 형태로 삽입
        heapq.heappush(leftheap, -num)

    # leftheap의 길이가 rightheap의 길이와 다르다면
    else:
        # rightheap에 현재 숫자를 삽입
        heapq.heappush(rightheap, num)

    # 양쪽 heap에 요소들이 존재한다면,
    # leftheap의 루트에 음수를 곱한 값이 rightheap의 루트보다 크다면
    if (len(leftheap) >= 1 and len(rightheap) >= 1 and -leftheap[0] > rightheap[0]):

        # leftheap의 루트를 제거하고, 
        leftroot = heapq.heappop(leftheap)
        # leftheap의 루트에 음수를 곱한 값을 rightheap에 삽입
        heapq.heappush(rightheap, -leftroot)

        # rightheap의 루트를 제거하고, 
        rightroot = heapq.heappop(rightheap)
        # rightheap의 루트에 음수를 곱한 값을 leftheap에 삽입
        heapq.heappush(leftheap, -rightroot)

    # leftheap의 루트에 음수를 곱한 뒤 출력
    print(-leftheap[0])