[백준] 2075 N 번째 큰 수 - 정렬(Sort) + 우선순위큐(PriorityQueue) JAVA

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

2075번: N번째 큰 수

코드설명

정렬(Sort) + 우선순위큐(PriorityQueue) 를 활용합니다.

 

문제에서 주어진 소개와는 상관없이, 다른 효과적인 방법을 찾아내야 한다는 점에서 좋은 문제라고 생각합니다.

 

문제에서 표의 채워진 수에 한 가지 특징이 있다, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것 이다. 라는 문구를 보면, 문제에서 뭔가 이러한 특징을 사용해야만 풀 수 있을 것 같이 느껴집니다. 

그렇기에, 처음에는 시작점을 기준으로 뭔가 규칙이 있는건가? 찾아보게 되고,,, 

아니면 숫자의 수 총 20억개를 다 만들어서 dp로 저장해야하나? (이 부분은 메모리제한 12MB 이기 떄문에 안됩니다.)

아니면 동적계획법으로, 시작위치에서 아래 위치까지 증가하는 부분 수열 문제인가? (이 부분은 각 열들이 서로 정렬되어있지 않기에 불가합니다.)

1500x1500 개의 map을 다 도면서 각 위치마다 나보다 큰 수가 Map에 몇개인지 구해서 그것이 N개일경우 중단하나? 라는 생각도 듭니다. 나보다 큰 수의 개수가 곧 내가 몇번쨰 N번쨰 수인지 알 수 있으니까요. (1500x1500x1500 = 10^6 * 15^3.. 연산개수를 보면, 시간초과가 나는 것을 알 수 있습니다. )

 

처음에, 어렵게 생각해서 고민했지만 아이디어만 떠오른다면 쉬운 문제였습니다.(아이디어 떠오르는것이 사실 가장 어렵습니다)

Arrays.sort가 아닌 PriorityQueue를 활용하여 pop을 N번 하도록 만들어도 가능합니다.

 

N(1 ≤ N ≤ 1,500)의 범위가 작기에 Arrays.sort로 정렬을 한뒤 진행하면됩니다.

Arrays.sort의 정렬 시간복잡도는 평균적으로는 O(N log (N) ) 이고, 최악의 경우 O(N^2) 입니다.

 

PriorityQueue 의 삽입 삭제 시간복잡도는 O(log N)의 시간이 걸립니다.

PriorityQUeue의 정렬은 O(N log N) 입니다.

우선순위큐를 활용하여 진행하는것이 빠를 것 입니다.확인결과 시간은 우선순위큐를 활용한 코드의 시간이 1.8배 빨랐습니다.

 

코드

단순히 정렬을 사용하여 진행

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	public static int N;
	public static int idx = 0;
	public static int answer = 0;
	public static int[] arr;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	arr = new int[N*N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			arr[idx++] = Integer.parseInt(st.nextToken()); 
    		}
    	}
    	
    	Arrays.sort(arr);
    	
    	System.out.println(arr[N*N - N]);
    }
    
}

우선순위큐를 활용하여 진행

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	public static int N;
	public static int idx = 0;
	public static int answer = 0;
	public static int[] arr;
	public static PriorityQueue<Node> pq = new PriorityQueue<>();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		for(int j=0;j<N;j++) {
    			pq.offer(new Node(Integer.parseInt(st.nextToken()))); 
    		}
    	}
    	
    	for(int i=0;i<N-1;i++) {
    		pq.poll();
    	}
    	
    	System.out.println(pq.poll().value);
    }
    
}
class Node implements Comparable<Node>{
	int value;
	
	public Node(int value) {
		this.value = value;
	}
	
	@Override
	public int compareTo(Node other) {
		if(this.value < other.value) {
			return 1;
		}else if(this.value > other.value){
			return -1;
		}else {
			return 0;
		}
	}
	
}

 

우선순위큐에 Collections.reverserOrder()를 사용하면 간단하게 내림차순으로 구현이 가능하다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, H, W, K;
	public static int answer = 0;
	public static int[][] matrix;
	public static PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		matrix = new int[N][N];
		for(int i=0;i<N; i++) {
			st = new StringTokenizer(br.readLine());	
			for(int j=0;j<N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
				pq.add(matrix[i][j]);
			}
		}
		
		while(!pq.isEmpty() && N - 1 > 0) {
			pq.poll();
			N-=1;
		}
		System.out.println(pq.poll());
	}
	

}