문제) 백준 - 우선수위 큐 - N번째 큰 수
https://www.acmicpc.net/problem/2075
2075번: N번째 큰 수
첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.
www.acmicpc.net
N * N개의 모든 수를 저장하고 정렬해서 N번째 큰 수를 구하기에는 메모리 제한이 12MB이기에 불가능합니다. 대부분의 정렬 문제는 우선순위 큐로 해결할 수 있습니다. 우선순위 큐를 최소 힙으로 사용하여 문제를 해결했습니다. Input을 최소 힙에 push 하면서 최소 힙이 N개가 되게 유지합니다. 그 후, top을 출력하면 해답을 구할 수 있습니다.
C++ 소스코드)
반응형
'PS(Problem Solving) > 백준_BOJ' 카테고리의 다른 글
| [백준] 2250번 - 트리의 높이와 너비 (C++) 문제 및 풀이 (0) | 2022.03.18 |
|---|---|
| [백준] 13302번 - 리조트 (C++) 문제 및 풀이 (0) | 2022.03.18 |
| [백준] 9935번 - 문자열 폭발 (C++) 문제 및 풀이 (0) | 2022.03.17 |
| [백준] 1613번 - 역사 (C++) 문제 및 풀이 (0) | 2022.03.16 |
| [백준] 1963번 - 소수 경로 (C++) 문제 및 풀이 (0) | 2022.03.16 |
댓글