728x90
문제
접근 방식
배열에 수를 모두 저장한 후에 정렬하고 끝에서 n번째 인덱스를 출력해도 풀리는 문제지만
우선순위 큐를 이용해서 좀 더 효율적으로 풀 수 있다.
최소 힙으로도 풀 수 있지만 최대 힙으로 푸는 것이 더 효율적이니
자바에서 제공하는 우선순위 큐 기준으로는 생성자 파라미터로 정렬 기준을
역순으로 주어 최대 힙을 사용할 수 있다.
최대 힙에 입력 받은 수들을 모두 넣어준 후에
n개를 꺼내면 n번째 큰 수가 나오게 된다.
풀이
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
int nNum = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
pq.offer(Integer.parseInt(st.nextToken()));
}
}
while (n-- > 0) {
nNum = pq.poll();
}
System.out.println(nNum);
}
}
'Java > Algorithms' 카테고리의 다른 글
[백준] 1655번 : 가운데를 말해요 (1) | 2024.01.22 |
---|---|
[백준] 1715번 : 카드 정렬하기 (1) | 2024.01.22 |
[백준] 1927번 : 최소 힙 (0) | 2024.01.22 |
[백준] 11286번 : 절댓값 힙 (1) | 2024.01.21 |
[백준] 18808번 : 스티커 붙이기 (0) | 2024.01.19 |