[백준] 1655번 - Python

문제 

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

 

 

 

---

문제 풀이 

 

1. 정렬

처음에는 단순하게 정렬로 문제를 접근했다.

N = int(input())
arr = []

for i in range(1,N+1):
  m = int(input())
  arr.append(m)
  
  raa = arr.copy()
  raa.sort()
  
  if i % 2 == 1:
    print(raa[i//2])
  else:
   print(raa[i//2-1])

 

배열에 값을 넣을 때마다 , 정렬해서 중간값을 뽑아내는 방법으로 구현을 했으나, 시간초과가 떠서 다른 방식으로 접근해야한다. 

 

2. 우선순위 큐(Priority Queue)

큐나 스택과는 달리, 각 원소들은 우선 순위를 가지고 있다.

우선순위 큐에서, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다.

같은 우선순위를 가진다면, 먼저 들어온 원소를 처리한다.

우선순위 큐는 heap 자료구조를 통해 구현이 가능하다. 

 

1. leftHeap(최대힙) , rightHeap(최소힙) 에 번갈아 넣어주면서 leftHeap 에서 pop하면 중간값 출력

2.rightHeap 에 원소를 넣을 때 leftHeap 원소보다 작은 값을 넣는다면 leftHeap 과 rightHeap 의 첫 원소를 교체 

3. sys.stdin.readline() 으로 작성

 

heap 이란?

완전 이진 트리의 형태를 가지며, Max Heap 에서는 부모 노드의 값이 자식 노드들의 값보다 항상 크거나 같다. 

Min Heap 에서는 부모 노드가 항상 자식 노드보다 작거나 같다. 루트 노드에 가장 큰 값이 위치한다.

 

Max Heap / Min Heap

 

우선순위 큐 구현

https://docs.python.org/ko/3/library/heapq.html

heapq — Heap queue algorithm

Min Heap 구현 가능 :  부모 노드의 값이 자식 노드의 값보다 항상 작거나 같은 완전 이진 트리로, 이러한 특성을 활용하여 최소값을 빠르게 추출할 수 있다.

 

heapq  주요 함수:

• heappush(heap, item): 힙 불변성을 유지하면서 item을 heap에 추가.

• heappop(heap): 힙에서 가장 작은 항목을 제거하고 반환.

• heapify(x): 리스트 x를 제자리에서 힙 구조로 변환.

• nlargest(n, iterable, key=None): iterable에서 가장 큰 n개의 요소를 반환.

• nsmallest(n, iterable, key=None): iterable에서 가장 작은 n개의 요소를 반환.

 

import heapq
import sys

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

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

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

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

        heapq.heappush(leftHeap, -rightValue)
        heapq.heappush(rightHeap, -leftValue)

    print(-leftHeap[0])