[백준 17829 / java] 222-풀링

문제

17829번: 222-풀링 (acmicpc.net)

풀이

재귀로 분류되어있는 문제이지만 구현으로 풀었다.

1. N*N 행렬을 여러 개의 2*2 행렬로 나눈다

2. 2*2 행렬에 포함된 수를 일차원 행렬에 넣어 Arrays.sort()로 정렬 -> 두 번째로 큰 숫자를 구한다

3. 도출된 숫자들로 이루어진 N/2*N/2 행렬을 만들어 같은 방식으로 진행한다

4. 1*1이 될 때까지 반복한 후 출력

코드 1

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

public class boj_17829 {
    static int[][] matrix;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        matrix = new int[N][N];
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++){
                matrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        while(N > 1){
            matrix = solve2(N);
            N /= 2;
        }
        bw.write(String.valueOf(matrix[0][0]));
        bw.close();
    }
    static int solve(int k, int m){ //2*2 행렬에서 두 번째로 큰 수 찾기
        int[] arr = new int[4]; //크기 비교를 위한 배열
        int count = 0;
        for(int i=k; i<k+2; i++){
            for(int j=m; j<m+2; j++){
                arr[count++] = matrix[i][j];
            }
        }
        Arrays.sort(arr);
        return arr[2]; //두 번째로 큰 수를 반환
    }

    static int[][] solve2(int size) { //행렬 축소
        int newSize = size/2;
        int[][] arr = new int[newSize][newSize];

        for (int i=0; i<size; i+=2) {
            for (int j=0; j<size; j+=2) {
                arr[i/2][j/2] = solve(i, j);
            }
        }
        return arr;
    }
}

 

코드 2

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

public class boj_17829_2 {
    static int[][] matrix;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        matrix = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                matrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        while(matrix.length > 1){
            matrix = pooling(matrix);
        }
        bw.write(String.valueOf(matrix[0][0]));
        bw.close();
    }
    static int[][] pooling(int[][] matrix){
        int size = matrix.length/2;
        int[][] ret = new int[size][size]; //리턴할 배열
        for(int i=0; i<size; i++){
            for(int j=0; j<size; j++){
                int _i = 2*i;
                int _j = 2*j;
                int[] t = new int[4]; //2*2배열의 값들을 정렬하기 위한 배열
                t[0] = matrix[_i][_j];
                t[1] = matrix[_i+1][_j];
                t[2] = matrix[_i][_j+1];
                t[3] = matrix[_i+1][_j+1];
                Arrays.sort(t);
                ret[i][j] = t[2];
            }
        }
        return ret;
    }
}

Note

• 코드 1 : 제한 시간 안에 문제를 풀어야 했는데 구글링을 통해 아이디어만 얻어서 짜본 코드. N*N배열에서 2*2배열을 얻을 때 인덱스를 얻는 방법을 생각해내기 어려웠다. 항상 이 부분에서 어려움이 느껴진다. 이번에는 for문의 i+=2 조건을 스스로 생각해내지 못했다. 
• 어쨌든 코드1, 코드2 모두 matrix의 00, 02, 04, ..., 20, 22, 24, 26, ...번째 인덱스에 접근한 뒤 해당 인덱스 기준 오른쪽, 아래, 오른쪽 아래 대각선 인덱스에 접근하는 방식은 똑같다.
• 물론 처음 코드 짤 때는 내가 짜고도 그렇게 구하고 있다는 사실을 몰랐다... 그냥 코앞에 놓인 문제를 해결하는 데만 급급한 채로 하나 하나 코드를 짰다. 그렇게 짜고 보니 코드가 한 눈에 안 들어오고 함수도 두 개나 생겼다. 함수명을 뭘로 정할지 생각하는 데에나 시간을 오래 쓰기도 했다..ㅋㅋ 
• 스터디에서 다른 사람이 나와 같은 방식으로 풀었다고 했지만 코드가 더 간결했다. 그래서 코드를 한 줄씩 해석해보고 똑같이 자바로 짜봤다. 그제서야 내가 짰지만 돌아가긴 하던(?) 코드1의 의미를 완전히 이해했고 인덱스에 접근할 때 i, j를 효율적으로 사용하는 감도 조금 익혔다. 
• 성능은 코드1이 코드2보다 메모리, 속도 면에서 더 좋았다.