[알고리즘] 크래프톤 정글 1주차 / 알고리즘 中 혼자서 못 푼 문제 정리2(가운데를 말해요)

BOJ 1655 가운데를 말해요

난이도 : (크래프톤 정글 기준) 중, (백준 난이도 기준) 골2

사용 알고리즘 or 자료 구조 : 우선순위 큐, 힙

처음 생각한 풀이

처음에는 중간 값을 찾아야하므로 최소힙, 최대힙(Min heap, Max heap)을 선언해야 한다고 생각했다.

하지만, 힙만 설정하고 어떻게 할 지 감을 못 잡아 주변 동료의 도움을 받았다.

도움 이후 풀이

Min heap과 Max heap, 그리고 중간 값을 담을 변수인 mid를 선언하고 시작한다.

 

차례대로 N개의 정수를 입력받는 순회가 시작하면, 처음에는 첫 번째 값을 mid로 설정하고 출력한다.

 

이후에 입력받는 정수들은 현재 mid와 비교하여 mid보다 크면 min heap에, mid보다 작으면 max heap에 push 한다.

push한 이후에는 min heap과 max heap의 크기를 비교하여 max heap이 min heap보다 크면 원래 mid를 min heap에 push해주고 max heap에서 정수를 하나 pop 하여 그 값을 mid로 설정한다.

이렇게 되면 min heap과 max heap의 크기를 맞출 수 있다.

 

여기서 포인트는 min heap이 max heap보다 큰 경우이다. 문제에서 중간 값이 두 가지 나올 경우(입력 받은 숫자의 개수가 짝수일 때 중간 인덱스가 2개가 나오게 된다), 더 작은 값을 출력하라고 했다.

min heap에 mid보다 큰 숫자들이 들어가므로 min heap의 크기는 max heap보다 1만큼 큰 것이 허용된다.

이 점을 고려하여 구현하도록 하자.

 

 

 

 

 

※ 스 포 주 의 ※

 

 

 

 

코드

import sys

from queue import PriorityQueue

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

maxpq = PriorityQueue()

minpq = PriorityQueue()

mid = 0

ans = []

for i in range(N):

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

    if i == 0:

        # 첫번째는 무조건 가운데 값

        mid = num

    else:

        if num >= mid:

            # 현재 mid와 비교해서 더 크면 minheap(min priority queue)에

            minpq.put(num)

        else:

            # 현재 mid와 비교해서 더 작으면 maxheap(max priority queue)에

            maxpq.put(-num)

    minsize = minpq.qsize()

    maxsize = maxpq.qsize()

    if minsize > maxsize and minsize - maxsize > 1:

        # min heap과 max heap의 크기를 비교해서 min heap의 크기가 더 크면 min heap에서 하나 빼서 mid, 원래 mid는 max heap으로

        # 크기 차이가 1 까지는 괜찮은 이유는 만약 중간 인덱스가 두 개 라면 더 작은 것을 출력하기 때문

        newmid = minpq.get()

        maxpq.put(-mid)

        mid = newmid

    elif maxsize > minsize:

        # min heap과 max heap의 크기를 비교해서 max heap의 크기가 더 크면 max heap에서 하나 빼서 mid, 원래 mid는 min heap으로

        newmid = -maxpq.get()

        minpq.put(mid)

        mid = newmid

    print(mid)