package backjoon17829;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
publicclassMain{
staticint N;
staticint[][] matrix;
publicstaticvoidmain(String[] args)throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
// 입력받은 수로 N * N 행렬 만드는 부분
matrix = newint[N][N];
for (int i = 0; i < N; i++) {
String[] s = br.readLine().split(" ");
for (int j = 0; j < N; j++) {
matrix[i][j] = Integer.parseInt(s[j]);
}
}
int size = N;
while (size > 1) { // N * N 행렬의 가로 세로가 1보다 클 때 까지 반복// 현재 행렬 가로(세로)길이를 2로 나눈 값을 제곱하면 다음 N * N 행렬을 만드는 데 필요한 수를 저장할 수 있는 1차원 배열의 사이즈를 알 수 있음// 예를 들어 현재 N * N 행렬의 가로(세로)길이가 8이면 (8 / 2)^2 = 16 -> 4 * 4의 행렬을 만들 수 있음// 그리고 고정된 2 * 2 크기의 행렬 안에서 두 번째 큰 수를 구해야 하므로 i, j를 +2 씩 증가 시키면서 반복, small_matrix에 저장int[] small_matrix = newint[(int) Math.pow(size / 2, 2)];
int idx = 0;
for (int i = 0; i < size; i += 2) {
for (int j = 0; j < size; j += 2) {
small_matrix[idx++] = getNum(i, j);
}
}
// N * N 행렬을 전체 탐색 후 크기를 반으로 줄임// 4 * 4 행렬로 예를 들면 small_matrix의 길이는 16이고 i = 0 ~ 15까지 반복하면서// row = 0 / 4 = 0, col = 0 % 4 = 0// row = 1 / 4 = 0, col = 0 % 4 = 1// row = 2 / 4 = 0, col = 0 % 4 = 2// row = 3 / 4 = 0, col = 0 % 4 = 3// row = 4 / 4 = 1, col = 4 % 4 = 0// row = 5 / 4 = 1, col = 5 % 4 = 1// row = 6 / 4 = 1, col = 6 % 4 = 2// row = 7 / 4 = 1, col = 7 % 4 = 3// 이런식으로 4 * 4 행렬의 값을 채워줄 수 있음
matrix = newint[size / 2][size / 2];
for (int i = 0; i < small_matrix.length; i++) {
int row = i / (size / 2);
int col = i % (size / 2);
matrix[row][col] = small_matrix[i];
}
// matrix에 새로운 값을 넣어준 후 size를 줄여줌
size /= 2;
}
// 맨 마지막에 남은 값 출력
System.out.println(matrix[0][0]);
}
publicstaticintgetNum(int row_start, int col_start){
// 두 번째 큰 수를 뽑기위한 내림차순 우선순위 큐
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
for (int i = row_start; i < row_start + 2; i++) {
for (int j = col_start; j < col_start + 2; j++) {
priorityQueue.offer(matrix[i][j]);
}
}
priorityQueue.poll();
return priorityQueue.poll();
}
}
- 우선순위 큐를 이용하면 두번째로 큰 수를 뽑는게 수월해진다. 메서드 getNum()
-> 우선순위 큐로 내림차순 정렬하여 두 번 poll()하면 두 번째로 큰 값이 나온다.
- while문을 실행할 때 새로운 1차원 배열 선언, smallMat[] 를 2차원 배열이 아닌 1차원 배열로 둔다.
-> board가 8 * 8행렬이면 네 칸 짜리 서브 배열이 64 / 4 = 16개 만들어진다. (while문 마지막에 board의 크기를 바꿔서 다시 선언하고 smallMat값을 각각 대입)
-> 그러면 16개의 구역에 대한 두 번째 작은 값을 각각 뽑아서 smallMat[idx++] = getNum(i, j) 에 저장한다.
-> 2차원 배열의 각 구역에서 두번째 작은 값을 => 1차원 배열에 각각 저장하고 => 2차원 배열에 다시 저장
-> 이 부분이 참신하다고 느꼈다. 비슷한 유형이 나오면 꼭 활용해야겠다.
- for(int i = 0;i < smallMat; ++i){} :
-> i / (size / 2) => 새로운 배열의 row,
-> i % (size / 2) => 새로운 배열의 col,
-> board[row][col] = smallMat[i];가 된다.
- for문에 i나 j가 단항 연산자로 쓰이지 않고 +2 할 수도 있다. (당연한 부분인데 코드가 낯설었다.)
MySol) 스터디원 코드 수정
java
열기
import java.util.*;
// 풀링publicclassTest5{
staticint[][] board;
staticint N;
publicstaticintgetNum(int _rowStart, int _colStart){
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for(int i = _rowStart; i < _rowStart + 2; ++i){
for(int j = _colStart;j < _colStart + 2; ++j){
pq.offer(board[i][j]);
}
}
pq.poll();
return pq.poll();
}
publicstaticvoidmain(String[] args){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
board = newint[n][n];
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
board[i][j] = scanner.nextInt();
}
}
int size = n;
while(size > 1){
int[] smallMat = newint[(int) Math.pow(size / 2, 2)]; // (n / 2) * (n / 2) => 1차원 배열로 선언int idx = 0;
for(int i = 0; i < size; i += 2){ // 행과 열을 모두 두 칸씩 이동for(int j = 0;j < size; j += 2){ //
smallMat[idx++] = getNum(i, j); // 두번째로 큰값을 넣는다.
}
}
board = newint[size / 2][size / 2];
for(int i = 0;i < smallMat.length; ++i){
int row = i / (size / 2);
int col= i % (size / 2);
board[row][col] = smallMat[i];
}
size /= 2;
}
System.out.println(board[0][0]);
}
}
