[JAVA]17829 222 풀링 - 분할 정복

 📚 문제  

17829번: 222-풀링

🔍 아이디어  

분할 정렬 문제로 정형적인 풀이로 풀면 됩니다.

 

매개변수:

n: 풀링 영역의 크기를 나타내는 변수입니다.

startX: 풀링 영역의 시작 X 좌표입니다.

startY: 풀링 영역의 시작 Y 좌표입니다.

반환값:

두 번째로 큰 값(풀링 값)을 반환합니다.

 

동작:

만약 n이 1인 경우, 주어진 startX와 startY에 해당하는 map의 요소 값을 반환합니다.

2x2 크기의 nMap 배열을 생성하고 nMap 배열의 요소값을 4등분으로 나눠 재귀적으로 호출합니다. 계산하여 구합니다.

이후에 2*2 배열을 돌며 두 번째로 큰 값을 찾아 반환합니다.

📝 풀이 

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

public class Main {
    private static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        map = new int[n][n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        System.out.println(findPooling(n, 0, 0));

    }

    private static int findPooling(int n, int startX, int startY) {
        if (n == 1) return map[startX][startY];

        int[][] nMap = new int[2][2];

        //4등분
        nMap[0][0] = findPooling(n / 2, startX, +startY);
        nMap[0][1] = findPooling(n / 2, startX, startY + n / 2);
        nMap[1][0] = findPooling(n / 2, startX + n / 2, startY);
        nMap[1][1] = findPooling(n / 2, startX + n / 2, startY + n / 2);


        int max = Integer.MIN_VALUE;
        int secondeMax = Integer.MIN_VALUE;

        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                int nowNum = nMap[i][j];
                if (max < nowNum) {
                    secondeMax = max;
                    max = nowNum;
                } else if (secondeMax < nowNum) {
                    secondeMax = nowNum;
                }
            }
        }

        return secondeMax;
    }
}