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

1. 문제

2. 아이디어

• 쉽게 생각하면 N^N개의 수 중에, N번 째로 큰 수를 구하는 것이다.
• 입력되는 수의 크기는 -10억 ~ 10억이지만, 수의 개수는 1500^2이므로 생각보다 연산 시간은 얼마 안걸리지 않을까 생각했다.

3. 코드

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

public class BOJ_2_2075 {
    public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(bf.readLine());
		int[] arr = new int[N*N];
		int idx=0;
		
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(bf.readLine());
			for(int j=0; j<N; j++) {				
				arr[idx++] = Integer.parseInt(st.nextToken());
			}
		}
		//System.out.println(Arrays.toString(arr));
		//[12, 7, 9, 15, 5, 13, 8, 11, 19, 6, 21, 10, 26, 31, 16, 48, 14, 28, 35, 25, 52, 20, 32, 41, 49]
		Arrays.sort(arr);
		//System.out.println(Arrays.toString(arr));
		// [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 19, 20, 21, 25, 26, 28, 31, 32, 35, 41, 48, 49, 52]
		System.out.println(arr[N*N-N]);
	}
}

4. 느낀점

• 해당 문제는 우선순위 큐를 쓰는 것이 보편적인 것 같다만, 떠오른 사고 과정대로 일단 풀어보았다.