DHistory
[Baekjoon] 정렬 - 2075 N번째 큰 수 본문
문제
https://www.acmicpc.net/problem/2075
풀이
우선 순위 큐 사용
1) 주어진 숫자를 구하고자하는 길이 만큼 넣는다.
2) 제일 작은 수보다 큰 숫자가 주어진 경우 제일 작은 수를 제외하고 큰 숫자를 넣는다.
예시
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 |
첫번째 줄
5, 7, 9, 12, 15
두번째 줄
13인 경우: 5, 7, 9, 12, 15 → 5제외 13추가 → 7, 9, 12, 13, 15
8인 경우: 7, 9, 12, 13, 15 → 7제외 8추가 → 8, 9, 12, 13, 15
11인 경우: 8, 9, 12, 13, 15 → 8제외 11추가 → 9, 11, 12, 13, 15
19인 경우: 9, 11, 12, 13, 15 → 9제외 19추가 → 11, 12, 13, 15, 19
6인 경우: 패스
...
코드
import sys
import heapq
n = int(sys.stdin.readline().rstrip())
queue = []
for _ in range(n):
numbers = list(map(int, sys.stdin.readline().rstrip().split()))
for number in numbers:
if len(queue) < n:
heapq.heappush(queue, number)
else:
if queue[0] < number:
heapq.heappop(queue)
heapq.heappush(queue, number)
print(queue[0])
'Computer Science > Algorithm' 카테고리의 다른 글
[Baekjoon] Graph - 5567 결혼식 (0) | 2024.08.27 |
---|---|
[Baekjoon] DP - 1965 상자넣기 (0) | 2024.08.22 |
[Baekjoon] DP - 11048 이동하기 (0) | 2024.08.20 |
[Baekjoon] DP - 9184 신나는 함수 실행 (0) | 2024.08.20 |
[Baekjoon] Graph - 16953 A → B (0) | 2024.08.20 |