[백준] 2075번 N번째 큰 수 자바

문제

 

2075번: N번째 큰 수

 

 

문제 풀이

 

처음에는 배열의 맨 아래 행만 정렬시킨 후 ArrayList에 담아, 두 개의 포인터를 이용해서 꺼내면서 이동시켜가면서 N번째 수를 구하려고 했는데 우선순위 큐를 이용하면 훨씬 빠르고 간단하게 풀이가 가능하다.

 

✔️ Priority Queue (우선순위 큐)

일반적인 FIFO인 큐의 구조를 그대로 가지는데, 데이터가 들어온 순서대로 나가는 것이 아니라 우선순위를 먼저 결정한 후 우선순위가 높은 데이터부터 나가는 자료구조이다.

 

N번째 큰 수를 구해야 하므로 큰 수부터 내려가기 위해 가장 아래 행을 봐야하고, 그 다음으로 가장 큰 수의 열을 살펴봐야 한다. 따라서 객체를 하나 더 만들어서 값과 행, 열 인덱스 값을 같이 담는다. 

배열의 마지막 행만 우선순위 큐에 담고, 하나씩 꺼내면서 꺼낸 값의 아래 열 값을 넣는다. 그러면 우선순위 큐에 들어간 값은 저절로 우선순위를 갖게 되므로 큰 수 부터 나오게 된다. 이렇게 N번째까지 반복한 후 종료하면 된다.

 

 

소스 코드

 

public class b_2075 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		PriorityQueue<Pair> pq = new PriorityQueue<>();
		int N = Integer.parseInt(br.readLine());
		int[][] arr = new int[N][N];
		
		for(int i = 0; i < N; i++) {
			String[] str = br.readLine().split(" ");
			
			for(int j = 0; j < N; j++) {
				arr[i][j] = Integer.parseInt(str[j]);
				if(i == N-1)
					pq.add(new Pair(i, j, arr[i][j]));
			}
		}
		
		//일단 맨 밑에서 큰 것부터 꺼내오자
		int count = 0;
		while(true) {
			if(count == N-1) {
				System.out.println(pq.poll().num);	//N번째 꺼내기
				break;
			}
			
			Pair cur = pq.poll();
			pq.add(new Pair(cur.r - 1, cur.c, arr[cur.r-1][cur.c]));
			count++;
		}

	}

}

class Pair implements Comparable<Pair>{
	int r, c, num;
	
	public Pair(int r, int c, int num) {
		this.r = r;
		this.c = c;
		this.num = num;
	}

	@Override
	public int compareTo(Pair arg0) {
		if(this.num > arg0.num)
			return -1;
		return 1;
	}
}