[백준] 2075번 : N번째 큰 수(JAVA)

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

2075번: N번째 큰 수

풀이

2가지 풀이 방법이 있습니다.

1. n * n 크기의 배열에 값을 다 넣고 정렬 후 뒤에서 n번째수 출력

2. pq(자동 정렬)에 값을 처음에 n개 넣고, 다음에 n * (n - 1)만큼 넣으면서 앞자리 1개씩 빼기 후 맨 앞수 출력

 

소스코드

1. 배열

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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

 

2. 우선순위 큐

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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