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

문제

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

풀이

• N*N의 표에서 수 N^2개가 채워져 있다.
• 모든 수는 자신의 한 칸 위에 있는 수보다 크다.
• N번째 큰 수를 출력하라.

방법은 크게, 3가지가 있습니다.

1. int 배열 사용

import java.util.*;
import java.io.*;

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

• int 배열에 전부 넣은 후, 이를 정렬한 다음 해당 인덱스에 존재하는 값을 꺼내왔습니다.
• 최대 힙보다는 아니지만 상당히 효율적입니다.

2. ArrayList 사용

import java.util.*;
import java.io.*;

public class Main {
	static int n;
	static List<Integer> nums;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		nums = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				int num = Integer.parseInt(st.nextToken());
				nums.add(num);
			}
		}
		
		Collections.sort(nums);
		
		System.out.println(nums.get(nums.size()-n));
	}
}

• 가변 배열에 모두 값을 넣어준 후 정렬한 다음, 정답 인덱스의 값을 꺼내왔습니다.

3. 최대 힙 사용

import java.util.*;
import java.io.*;

public class Main {
	static int n;
	static PriorityQueue<Integer> pq;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		pq = new PriorityQueue<>(Collections.reverseOrder());
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				int num = Integer.parseInt(st.nextToken());
				pq.add(num);
			}
		}
		
		for (int i = 0; i < n - 1; i++) {
			pq.poll();
		}
		
		System.out.println(pq.poll());
	}
}

• 이 중 가장 효율적인 코드입니다.
• PriorityQueue는 값을 넣을 때 배열 안에 있는 값들을 오름차순으로 정렬하는 성질이 있습니다.
• 이를 역순으로 넣어주게 되면 최대 힙으로 사용할 수 있습니다.
• 선언할 때, Collections.reverseOrder()를 같이 선언하면 최대 힙 구현이 가능합니다.
• 마지막에 n-1개를 빼주고 그 다음 값을 pop하시면, 정답을 구할 수 있습니다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n;
	static PriorityQueue<Integer> pq;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		pq = new PriorityQueue<>(Collections.reverseOrder());
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				int num = Integer.parseInt(st.nextToken());
				pq.add(num);
			}
		}
		
		for (int i = 0; i < n - 1; i++) {
			pq.poll();
		}
		
		System.out.println(pq.poll());
	}
}