사실 그럴 필요 없다
파이썬 짱짱맨
1927번 - 최소 힙
https://www.acmicpc.net/problem/1927
입력값이 0이면 최소 힙의 pop을, 0이 아닌 정수 (자연수로 제한됨)이면 그 수를 힙에 집어넣으면 되는 문제
첫 번째 풀이
import sys
from collections import deque
def sortInsert(minHeap, x):
if len(minHeap) == 0:
minHeap.append(x)
return
start = 0
end = len(minHeap) - 1
while (start <= end):
mid = (start + end) // 2
if minHeap[mid] > x:
end = mid - 1
else:
start = mid + 1
minHeap.insert(end+1, x)
return
def solution():
n = int(sys.stdin.readline())
minHeap = deque()
for _ in range(n):
x = int(sys.stdin.readline())
if x == 0:
if len(minHeap) != 0:
print(minHeap.popleft())
else:
print(0)
else:
sortInsert(minHeap, x)
solution()힙에 뭔가 들어있으면 이진 탐색 → 위치 찾기 → 삽입
이 코드의 시간 복잡도 (최악의 경우)는 아래와 같이 계산할 수 있다.
1. n (들어올 명령의 수)만큼 반복문을 실행 → O(N)
2. sortInsert에서 이진 탐색 → O(logN)
3. sortInsert에서 heap.insert() 사용 → O(N)
minHeap을 deque으로 정의해서 삽입/삭제 모두 O(1)이라고 생각하고 코드를 짰다....
하지만 insert는 큐의 한가운데 있는 특정 위치에 삽입하는 것이므로 리스트의 삽입/삭제와 비슷하게 동작한다. (맨 뒤에 한 칸 더 만들고 맨 뒤로 다 밀고 집어넣음 → 최악의 경우 O(N))
결론: O(N * (logN + N)) → O(N^2)
N은 최대 100,000 이고, 시간 제한이 1초이므로... 딱걸렸잔슴
파이썬에는 heapq라는 라이브러리가 있는데 요것을 사용하지 않고 풀던 대로 풀려면 탐색 → 삽입에 들어가는 시간을 단축시켜야 한다.
두 번째 풀이
import sys
from collections import deque
def insert(minHeap, x):
minHeap.append(x)
index = len(minHeap) - 1
while (index != 1 and x < minHeap[index//2]):
minHeap[index], minHeap[index//2] = minHeap[index//2], minHeap[index]
index = index // 2
def delete(minHeap):
minHeap[1], minHeap[-1] = minHeap[-1], minHeap[1]
print(minHeap.pop())
index = 1
while (True):
child = index * 2
if child + 1 < len(minHeap) and minHeap[child] > minHeap[child+1]:
child += 1
if child >= len(minHeap) or minHeap[child] > minHeap[index]:
break
minHeap[child], minHeap[index] = minHeap[index], minHeap[child]
index = child
def solution():
n = int(sys.stdin.readline())
minHeap = deque()
minHeap.append(-1)
for _ in range(n):
x = int(sys.stdin.readline())
if x == 0:
if len(minHeap) != 1:
delete(minHeap)
else:
print(0)
else:
insert(minHeap, x)
solution()minHeap의 insert/delete를 구현한다.
1. insert: O(logN)
- 맨 위에 (deque의 맨 앞에) 집어넣고 자식과 비교하면서 내려간다.
- delete: O(logN)
- root 노드를 삭제, 맨 마지막 leaf 노드 (deque의 맨 마지막 요소)를 root 자리에 넣고 비교하면서 자리를 찾는다.
- solution: O(N)
결론: O(N * (logN + logN)) = O(NlogN)
- swap은 트리의 높이만큼 수행한다. h = logN
세 번째 풀이 (heapq)
import sys, heapq
heap = []
for _ in range(int(sys.stdin.readline())):
x = int(sys.stdin.readline())
if x == 0:
if len(heap) == 0:
print(0)
else:
print(heapq.heappop(heap))
else:
heapq.heappush(heap, x)heapq.heappop(heap), heapq.heappush(heap, 넣을 거)
이 두가지를 쓸 줄 알면 후다닥 풀 수 있는 문제였다.
heap으로 쓸 수 있는 건 리스트
- []로 초기화한 리스트를 만들거나
- heapify(list)를 통해서 이미 존재하는 리스트를 힙으로 바꿀 수 있다
https://docs.python.org/ko/3/library/heapq.html
그냥...
뭔가 삽입/삭제가 많을 것 같아서 deque을 썼는데 큰 의미 없었던 것 같기도 하고
자료구조 좀 열심히 들을걸 그랬다
이런!
역시 불성실은 언제나 업보로 돌아오는구만
