https://www.acmicpc.net/problem/2075
풀이 ①
1. 아이디어
- 입력 행렬의 모든 수를 1차원 배열에 저장
- 배열 정렬하여, n 번째 큰 수
[length - n]출력
2. 자료구조
int[]: 행렬의 수들 저장
3. 시간 복잡도
- 행렬 입력: O(n^2)
- 배열 정렬: O(N log N) (N: 정렬 item 개수)
=> N = n^n => n 최대값 입력: 1,500 x 1,500 = 2,250,000 개 item 정렬
=> 2,250,000 x log(2,250,000) = 2,250,000 x log(225 x 10^4)
= 2,250,000 x [log(225) + log(10^4)]
~= 2,250,000 x (3 + 4)
~= 15,750,000 << 1억 (1초)
코드
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main_Sort {
static int n;
static int[] numbers; // n x n 행렬의 총 n^2 개의 수를 담은 배열
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(
new InputStreamReader(System.in)
);
StringTokenizer st;
n = Integer.parseInt(br.readLine());
numbers = new int[n * n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++)
numbers[i * n + j] = Integer.parseInt(st.nextToken());
}
Arrays.sort(numbers);
System.out.println(numbers[numbers.length - n]); // n 번째 큰 수
}
}풀이 ②
1. 아이디어
- 입력 n x n 행렬의 모든 수들을
PriorityQueue에 입력
=>PriorityQueue에 수들이 내림차순으로 정렬되도록 함
2. 자료구조
int[][]: 행렬
=> 20억이 안되므로 int 가능PriorityQueue<Integer>: 행렬에 적힌 수 입력하여 내림차순 정렬
3. 시간 복잡도
PriorityQueue의 시간 복잡도
=> 삽입 / 삭제: O(log n) (n: 노드 개수)
코드
import java.io.*;
import java.util.Collections;
import java.util.StringTokenizer;
import java.util.PriorityQueue;
public class Main_PriorityQueue {
static int n;
static int[][] numbers; // n x n 행렬에 입력된 n^2 개의 수
static PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
static int solution() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
pq.add(numbers[i][j]);
}
// 앞에서부터 n-1 개 버림
for (int i = 1; i <= n - 1; i++)
pq.remove();
return pq.peek(); // n 번째 큰 수
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(
new InputStreamReader(System.in)
);
StringTokenizer st;
n = Integer.parseInt(br.readLine());
numbers = new int[n][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++)
numbers[i][j] = Integer.parseInt(st.nextToken());
}
System.out.println(solution());
}
}풀이 ③
1. 아이디어
PriorityQueue에 최대 n 개의 수만 저장되도록 관리하면서 저장
=> 최초 n개의 수들을PriorityQueue에 저장하고,
이후 부터는add(new item),remove()반복
!!! 반드시add(new item),remove()순서로 할 것PriorityQueue의 내부 Heap 크기를 최소로 유지하여 삽입 / 삭제 속도를 높임
2. 자료구조
int[][]: 행렬
=> 20억이 안되므로 int 가능PriorityQueue<Integer>: 행렬에 적힌 수 입력하여 오름차순 정렬
3. 시간 복잡도
PriorityQueue의 시간 복잡도
=> 삽입 / 삭제: O(log n) (n: 노드 개수)
PriorityQueue에 최초 n개 입력: log 1 + log 2 + ... + log n
= log (1 x 2 x ... x n) = log(n!) = n log n- 이후
pq.add(),pq.remove()반복: n(n-1) x 2 log n
=> 총 n log n + n(n-1) x 2 log n
=> n 최대값 대입: 1500 log 1500 + 1500(1500-1) x 2 log 1500
~= 1500 x 4 + 1500 x (1500-1) x 2 x 4
= 6,000 + 2,248,500 x 8
= 17,994,000 << 1억 (1초)
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main_PriorityQueue_Upgrade {
static int n;
static int[][] numbers;
static PriorityQueue<Integer> pq = new PriorityQueue<>();
static int solution() {
// 최초 입력 행렬에서 n개 수들을 pq에 저장
for (int i = 0; i < n; i++)
pq.add(numbers[0][i]);
// 이후 부터는 add(new item), remove 반복
for (int i = 1; i < n; i++) {
for (int j = 0; j < n; j++) {
pq.add(numbers[i][j]);
pq.remove();
}
}
return pq.peek();
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(
new InputStreamReader(System.in)
);
StringTokenizer st;
n = Integer.parseInt(br.readLine());
numbers = new int[n][n];
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++)
numbers[i][j] = Integer.parseInt(st.nextToken());
}
System.out.println(solution());
}
}Priority Queue / Heap의 시간 복잡도
- Priority Queue 는 내부적으로 Heap 으로 구현됨
- 삽입 / 삭제: O(lg n) (n: 노드 개수)
=> 노드 수 n을 최소(내부 Heap 크기를 최소)로 유지하면서,
Priority Queue를 사용하는 것이 바람직
Arrays.sort() 보다 PriorityQueue를 사용하는 것이 더 유리한 경우
- 특정 n 번째(n 개) 큰 수 등을 찾을 때
=> Priority Queue에서 저장 노드 개수를 n으로 유지- 입력을 받는 도중, 실시간으로
n 번째 큰 수 등을 갱신해야 하는 경우
Silver Star