1. 백준-11279 최대힙, 1927 최소힙
https://www.acmicpc.net/problem/11279
https://www.acmicpc.net/problem/1927
2. 알고리즘 카테고리 : 힙
3. 나의 풀이 알고리즘(1차) : 힙
import heapq
max_heap = []
input_count = int(input())
for _ in range(input_count):
i = int(input())
if i == 0:
if len(max_heap) == 0:
print(int(i))
else:
print(-heapq.heappop(max_heap))
else:
heapq.heappush(max_heap, -i)
- 여기서 시간초과 문제가 발생하였다. N이 10^5이고, N에 대하여 heappop NlogN, heappush NlogN이기 때문에 시간 복잡도에서 문제가 없었다. 코드에 문제가 없다면 외부에서 데이터를 불러오는 과정에서 시간이 초과되는 것이라고 유추를 해볼 수 있다.
- 찾아보았더니 input() 내장함수 자체가 문자열로 변환, strip을 수행한 뒤 반환하기 때문에 느리다는 것을 알게 되었다. 따라서 sys.stdin과 readline으로 수행하도록 코드를 수정하였다.
나의 풀이 알고리즘(2차) : 힙
import heapq
import sys
lines = []
for line in sys.stdin:
lines.append(line)
lines.reverse()
max_heap = []
input_count = int(lines.pop())
for _ in range(input_count):
print(f'max_heap: {max_heap}')
i = int(lines.pop())
if i == 0:
if len(max_heap) == 0:
print(0)
else:
print(-heapq.heappop(max_heap))
else:
heapq.heappush(max_heap, -i)
'알고리즘' 카테고리의 다른 글
[백준-2583] 영역 구하기 #DFS #BFS (0) | 2024.06.24 |
---|---|
[Leetcode-42] Trapping Rain Water #투포인터 (0) | 2023.12.28 |
[프로그래머스-42577] 전화번호목록 #해시(Hash) #트라이(Trie) #세트(Set) (0) | 2023.06.27 |