문제 📕

N×N의 표에 수 N^2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

(https://www.acmicpc.net/problem/2075)

접근 방법 🧐

우선순위큐

만 안다면 역시나 쉽게 풀 수 있는 문제다. 이전 문제에서 우선순위 큐에대해 알아버렸기 때문에 금방 풀었다.
우선순위큐에대해 처음 공부하고 푼 문제

• 우선순위큐는 기본적으로 오름차순으로 정렬이 된다.
• 하지만 예제상으로 5번째, 즉 N번째 큰 수를 찾아야하니까 내림차순으로 정렬이 되면 편할 것이다.

우선순위 큐 선언할 때

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

이렇게 하면 오름차순으로 내부적으로 값이 정렬된다!!

• 찾는 값이 맨 앞으로 올 때 까지 맨 앞 값을 계속 제거해주고, N번째 값을 출력해주도록 했다.

내가 쓴 코드 ✍️

import java.util.*;
import java.io.*;
public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				pq.add(Integer.parseInt(st.nextToken()));
			}
		}
		
		for(int i=0;i<N-1;i++) {
			pq.remove();
		}
		bw.write(pq.poll()+"");
		bw.flush();
		bw.close();
	}
}

느낀점 📖

우선순위큐 제법 익숙해진듯! 이제 우선순위큐를 사용한 문제인지 아닌지 잘 판단하고 잘 쓰면 되겠다.