[백준1655번] 가운데를 말해요 / Python3

문제

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

예를 들어 수빈이가 동생에게 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

7
1
5
2
10
-99
7
5

예제 출력 1

1
1
2
2
2
2
5

나의 풀이

이 문제는 검색을 통해서 풀이법을 찾아보게 되었다. 최소 힙과 최대 힙을 사용해서 중간값을 찾는 것이 그 풀이법이었다.

다음 두가지 조건을 맞게끔 알고리즘을 구현해주면 중간값을 구할 수 있다.

1) 최대 힙의 크기는 최소 힙의 크기와 같거나 1만큼 커야한다.

2) 최소 힙의 최소 값이 최대 힙의 최대 값보다 크거나 같아야한다. (짝수일때 작은값을 반환해주는 것과도 연관있음.)

  => 두 조건이 맞을 때 최대 힙에서 최대 값이 곧 중간값이 된다.

예를들어 1,3,5,7,9를 이 알고리즘에 따르게 그림으로 표현하면 다음과 같다.

1. 

• 처음에는 최대 힙에 넣어준다. 자연스럽게 최대 힙에 있는 하나의 값이 중앙값이 된다.

2. 

• 3이 최대 힙에 들어가면 조건 1)이 위배된다. 따라서 최소 힙으로 들어가야 한다. 그리고 조건 2)를 확인해보면 3 < 1이므로 성립된다. 따라서 중간값은 최대 힙에 있는 최댓값 1이 된다. ( 짝수일경우 중간 두개 중 작은 값 )

  
  

3. 

• 조건 1)에 의해 5는 최대 힙에 들어간다. 넣고보면 3 < 5로 조건 2)가 위배된다. 그러므로 3과 5를 서로 바꾸어준다. 따라서 중간값은 최대 힙의 최댓값인 3이 된다.

4. 

• 조건 1)에 의해 7이 최소 힙으로 들어가게되고 조건 2)가 위배되지 않으므로 바꾸지않는다. 따라서 중간값은 3이다.

5. 

• 3을 넣었을때와 마찬가지로 최대 힙에 9가 들어가지만 조건 2)에 위배되므로 5와 9가 바뀌어서 중간값은 5가 된다.

파이썬의 heapq를 사용하여 문제를 풀었다. 주의할 점은 역시 heapq는 최소 힙이라는 점이다. 따라서 최대 힙에 넣을때는 -1을 곱하고 빼서 출력을 해줄때에도 -1을 곱해주어야 한다는 점이다.

• 참고 : https://www.crocus.co.kr/625

코드

# 1655번 가운데를 말해요
import sys
import heapq

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

maxHeap = []    # 최대힙
minHeap = []    # 최소힙
for _ in range(n):
    num = int(sys.stdin.readline())

    # 1번 조건
    if len(maxHeap) == 0:
        heapq.heappush(maxHeap, -1 * num)
    elif len(minHeap) == len(maxHeap):
        heapq.heappush(maxHeap, -1 * num)
    else:
        heapq.heappush(minHeap, num)

    # 2번 조건
    if len(minHeap) != 0 and len(maxHeap) != 0 and minHeap[0] < (-1 * maxHeap[0]):
        tmp_min = heapq.heappop(minHeap)
        tmp_max = heapq.heappop(maxHeap)

        heapq.heappush(maxHeap, -1 * tmp_min)
        heapq.heappush(minHeap, -1 * tmp_max)

    print(-1 * maxHeap[0])