(백준) 1655 가운데를 말해요 문제 코드 분석 (상세하게)

<포스팅 요약>

1. 문제풀러가기

2. 문제 해결 코드

3. 로직 분석

4. 코드 분석

---

1. 문제풀러가기

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

1655번: 가운데를 말해요

 

문제 해석:

예시 입력	예시 출력
7 1 5 2 10 -99 7 5	1 1 2 2 2 2 5

 

> 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다.

> 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

 

1 => 중간값 : 1

1, 5=> 짝수이므로 min(1,5) =>중간값 : 1

1, 5, 2 => 정렬: 1, 2, 5 => 중간값: 2

1, 5, 2, 10 =>정렬: 1, 2, 5, 10 => 짝수이므로 min (2,5) => 중간값 : 2

1, 5, 2, 10, -99 => 정렬: -99, 1, 2, 5, 10 => 중간값: 2

1, 5, 2, 10, -99, 7 => 정렬: -99, 1, 2, 5, 7, 10 => 짝수이므로 min(2,5) => 중간값: 2

1, 5, 2, 10, -99, 7, 5  => 정렬: -99, 1, 2, 5, 5, 7, 10 => 중간값: 5

---

2. 문제 해결 코드

import heapq
import sys

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

leftHeap = []
rightHeap = []
for i in range(N):
    n = int(sys.stdin.readline())

    if len(leftHeap) == len(rightHeap):
        heapq.heappush(leftHeap, -n)
    else:
        heapq.heappush(rightHeap, n)

    if rightHeap and rightHeap[0] < -leftHeap[0]:
        right = heapq.heappop(rightHeap)
        left = heapq.heappop(leftHeap)

        heapq.heappush(leftHeap, -right)
        heapq.heappush(rightHeap, -left)

    print(-leftHeap[0])

코드 참고: https://hongcoding.tistory.com/93

(**홍코딩님의 코드를 참고하였으며, 위 링크의 포스팅에 코드 설명이 잘되어있으니

부족한 부분은 홍코딩님의 포스팅 참고 바랍니다.)

 

---

3. 로직 분석

로직 요약 : 

1. leftHeap배열과 rightHeap배열이 있으면 (leftHeap과 rightHeap모두 힙정렬된 배열),

숫자를 차근차근 leftHeap과 rightHeap에 번갈아 가며 채워준다.

2. 이때 중간값은 무조건 leftHeap에서 제일 큰 숫자이다.

3. 만약 rightHeap에서 제일 작은 숫자가 leftHeap보다 작을 경우,

leftHeap의 제일 큰 숫자와 rightHeap의 제일 작은 숫자의 위치를 바꿔 준 후, leftHeap에서 제일 큰 숫자를 출력해준다.

 

힙정렬 사용하는 이유 : 

> 다른 숫자들의 정렬은 신경쓸 필요 없이,

leftHeap에서는 가장 큰 숫자, rightHeap에서는 가장 작은 숫자만 비교하면 된다.

> 힙정렬을 사용하면, 가장 큰 숫자와 작은 숫자만 간단하게 비교할 수 있다.

> leftHeap의 경우, 최대힙(max heap)을 사용하여 leftHeap[0]에 항상 제일 큰 숫자가 위치하게 하고,

rightHeap의 경우, 최소힙(min heap)을 사용하여 rightHeap[0]에 항상 제일 작은 숫자가 위치하게 한다.

(** 아래 그림 참고하세요)

---

4. 코드 분석

 

leftHeap = []
rightHeap = []

if len(leftHeap)==len(rightHeap):
	heapq.heappush(leftHeap,-n)

 

len(leftHeap) == 0, len(rightHeap)==0 으로 길이가 동일하므로,

첫번째 입력된 숫자를 leftHeap에 넣어준다.

 

** -n으로 한 이유는 파이썬에서 힙정렬은 기본적으로 최소힙(min Heap)으로 정렬된다.

최대 힙으로 정렬하려면 push할때 -(마이너스)를 붙이고,

pop하거나 출력할때 -(마이너스)를 붙여서 출력하면 된다.

 

 

여기서 rightHeap은 null이므로 아래 조건은 만족하지 않아 넘어간다.

if rightHeap and rightHeap[0] < -leftHeap[0]:
        right = heapq.heappop(rightHeap)
        left = heapq.heappop(leftHeap)

        heapq.heappush(leftHeap, -right)
        heapq.heappush(rightHeap, -left)

 

 

아래 코드로 인하여 중간값 1을 출력한다.

 print(-leftHeap[0])

 

아래 숫자들도 위와 같은 로직으로 동작한다. ( 그림 참고하세요)