백준 2075 - N번째 큰 수 (파이썬)
글 작성자: pental
https://www.acmicpc.net/problem/2075
풀이
문제의 핵심은 메모리 초과이다 N * N 크기의 행렬을 모두 메모리에 저장만 하더라도 메모리 초과가 일어나기 때문이다.
이를 효율적으로 처리하기 위해 우선순위 큐를 사용해 효율적으로 해결한다.
- 행령을 읽어, 읽어온 각 숫자를 처리하며, 각각의 방식으로 힙을 유지한다.
- 힙 크기가 N보다 작은 경우
- 그냥 heapq.heappush()로 추가
- 힙 크기가 N과 같거나 큰 경우
- 만약 현재 힙의 최솟값 보다 큰 숫자가 들어오면, heapq.heappush()를 통해 추가한 후, heapq.heappop()으로 가장 작은 수를 제거하여 힙 크기를 N개로 유지한다.
시간 복잡도
- 입력이 N*N이므로 총 N^2개의 숫자를 처리해야한다,
- 각 숫자에 대해 heappush() 및 heappop()연산을 수행하며, 이는 O(logN)의 시간복잡도를 가진다,
- 따라서 총 시간 복잡도는 O(N^2LogN)이다.
코드
# 백준 2075 - N번째 큰 수
# 분류 : 우선순위 큐
import heapq
N = int(input())
heap = []
for _ in range(N) :
a = list(map(int, input().split()))
for j in a :
if len(heap) < N :
heapq.heappush(heap, j)
else :
if heap[0] < j :
heapq.heappush(heap, j)
heapq.heappop(heap)
print(heap[0])
'Programming > 백준' 카테고리의 다른 글
백준 1302 - 베스트셀러 (파이썬) (0) | 2025.03.13 |
---|---|
백준 1092 - 배 (파이썬) (0) | 2025.03.12 |
백준 16439 - 치킨치킨치킨 (0) | 2025.03.11 |
백준 17255 - N으로 만들기 (파이썬) (0) | 2025.03.10 |
백준 13164 - 행복 유치원 (파이썬) (0) | 2025.03.10 |
댓글
이 글 공유하기
다른 글
-
백준 1302 - 베스트셀러 (파이썬)
백준 1302 - 베스트셀러 (파이썬)
2025.03.13 -
백준 1092 - 배 (파이썬)
백준 1092 - 배 (파이썬)
2025.03.12 -
백준 16439 - 치킨치킨치킨
백준 16439 - 치킨치킨치킨
2025.03.11 -
백준 17255 - N으로 만들기 (파이썬)
백준 17255 - N으로 만들기 (파이썬)
2025.03.10