[BOJ] 백준 1655 가운데를 말해요 Python

 

1655번: 가운데를 말해요

문제
백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.예를 들어 백준이가 동생에게 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보다 크거나 같고 100,000보다 작거나 같은 자연수이다.
즉, 배열로 문제를 정렬하면서 풀면 최악의 상황에선 O(n²)이다. 그럼 최악의 상황에선 100,000 x 100,000의 시간복잡도를 가지기에 배열로 정렬하며 푸는것은 적절하지 않다.

따라서 우선순위 힙을 적용해서 이 문제에 접근했다.
최대힙,최소힙 두개를 만들어 번갈아가며 새로 주어진 입력값을 넣고 만약 오른쪽힙(최소힙)의 최소값(0번노드)이 왼쪽힙(최대힙)의 최소값(0번노드)보다 작다면  중간값은 왼쪽힙의 0번째 노드로 설정이 되지 않기때문에 서로의 0번노드를 교체해준다. 이렇게 하면 왼쪽 최대힙의 0번째 노드에는 항상 중간값이 위치하게  된다.

문제풀이 순서
1. n을 입력받는다.
2. 왼쪽 힙(최대힙), 오른쪽 힙(최소힙)으로 힙을 2개 생성한다.
3. 새로운 숫자를 입력받으며 길이가 같으면 왼쪽 힙에 push,  다르면 오른쪽 힙에 push해준다.
4. 오른쪽 힙의 0번노드가 왼쪽 힙의 0번노드보다 값이 작으면 서로를 교체해준다. (왼쪽힙의 0번노드에 중간값을 배치하기 위함)
5. answer_list에 append 하고 마지막에 답을 출력해준다.

---

Code

  

    
    
    
    
  
import heapq
import sys
n = int(sys.stdin.readline())
left_hq = []
right_hq = []
answer_list = []
for i in range(n):
    new = int(sys.stdin.readline())
    if len(left_hq) == len(right_hq):
        heapq.heappush(left_hq, -new)
    else:
        heapq.heappush(right_hq, new)
    if right_hq and right_hq[0] < -left_hq[0]:
        left_value = heapq.heappop(left_hq)
        right_value = heapq.heappop(right_hq)
        heapq.heappush(left_hq, -right_value)
        heapq.heappush(right_hq, -left_value)
    answer_list.append(-left_hq[0])
for i in answer_list:
    print(i)