문제
N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.
12 | 7 | 9 | 15 | 5 |
13 | 8 | 11 | 19 | 6 |
21 | 10 | 26 | 31 | 16 |
48 | 14 | 28 | 35 | 25 |
52 | 20 | 32 | 41 | 49 |
이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.
입력
첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.
출력
첫째 줄에 N번째 큰 수를 출력한다.
코드
import heapq
N = int(input())
heap = []
for _ in range(N):
row = list(map(int,input().split()))
for num in row :
if len(heap) < N:
heapq.heappush(heap, num)
else:
if num > heap[0] :
heapq.heappop(heap)
heapq.heappush(heap, num)
print(heap[0])
코드풀이
N번째 최댓값을 구하기 위하여 최소힙을 사용하였다.
힙을 N칸까지만 유지하여, N번째 후 부터는 힙의 최솟값과 새로 추가되는 값을 비교한다.
힙 내부의 최솟 값보다 큰 경우 힙의 최솟값을 pop하고 새 값을 push 한다.
연산을 완료한 후 힙의 최솟값을 출력한다.
'Koala - 19기 > 코딩테스트 심화 스터디' 카테고리의 다른 글
[백준/python] 16401 : 과자 나눠주기 (0) | 2025.07.07 |
---|---|
[BOJ/C++] 3273번: 두 수의 합 (0) | 2025.07.06 |
[python/백준] 1935: 후위 표기식2 (0) | 2025.07.06 |
[백준/Python] #7662: 이중 우선순위 큐 (0) | 2025.07.06 |
[PYTHON/백준] 11279 최대힙 (0) | 2025.07.06 |