[백준] 17829번 222-풀링

문제링크: 백준 17829 222-풀링

---

1. 아이디어

2x2 행렬까지 들어간 후 2번째로 큰 값을 구하면서 점점 나오는 구조.
2x2 행렬에서는 4개의 숫자를 구한 후 정렬을 하여 뒤에서 2번째 수를 리턴하면 된다.
2x2 행렬이 될 때까지 재귀함수로 깊이 들어감.
단, 재귀에서 나올 때 2번째 수를 가지고 나와야 한다.

1. 시간복잡도

행렬의 가로(세로) N: 2 <= N <= 1,024
재귀호출의 최대 횟수: 최대 크기인 1,024x1,024를 2x2로 쪼개면 2^9 * 2^9 = 2^18개 = 262,144번
Arrays.sort정렬: O(N^2) => 1,024x1,024 = 1,048,576번
=> 연산량 1억번 넘지 않음

1. 자료구조

행렬의 가로(세로) N: 2 <= N <= 1,024 ==> int 가능

---

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

public class Main {
    public static int[][] grid;
    public static int n;
    public static int solution(int x, int y, int n) {
        return pulling(0, 0, n);
    }

    // 사각형이 더 쪼갤 수 있으면 재귀호출
    public static int pulling(int x, int y, int n) {
        // 마지막 재귀에 도착했을땐 2x2 배열일때.
        // 이때 a,b,c,d를 가지고 2번째 숫자 구해줘서
        int a = grid[x][y];
        int b = grid[x+1][y];
        int c = grid[x][y+1];
        int d = grid[x+1][y+1];
        // 만약 2보다 크면 계속 재귀 먼저 들어감
        // 그리고 다 하고 나올때는 거기서 계산해온 2번째 큰 값 가지고 나옴
        if(n != 2) {
            a = pulling(x, y, n / 2);
            b = pulling(x, y + (n / 2), n / 2);
            c = pulling(x + (n / 2), y, n / 2);
            d = pulling(x + (n / 2), y + (n / 2), n / 2);
        }
        // pulling 재귀함수의 리턴값으로 밖으로 내보냄
        return secondNum(a, b, c, d);
    }
    // 2번째 큰 수 추출, 매개변수는 2X2 배열의 구성요소
    public static int secondNum(int a, int b, int c, int d) {
        int[] arr = new int[4];
        arr[0] = a;
        arr[1] = b;
        arr[2] = c;
        arr[3] = d;
        Arrays.sort(arr);
        return arr[2];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        grid = new int[n][n];
        for (int i = 0; i < n; i++) {
            String[] s = br.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                grid[i][j] = Integer.parseInt(s[j]);
            }
        }
        System.out.println(solution(0, 0, n));
    }
}

• 학습내용

들어가면서 계산해서 끝내는게 아니라 다 들어간 다음에 나오면서 계산을 완성해가는 것은
재귀해서 나온 값을 변수에 받아 나와야 한다. (위 문제에서는 pulling 메서드를 변수 a, b, c, d로 각각 받음)

• 다른 풀이

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int[][] map;
	static int N;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		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());
			}
		}
		int answer = parse(N,0,0);
		System.out.println(answer);
	}

	private static int parse(int n,int r, int c) {
		if(n==2) {
			int[] ary = new int[4];
			ary[0] = map[r][c];
			ary[1] = map[r][c+1];
			ary[2] = map[r+1][c];
			ary[3] = map[r+1][c+1];
			Arrays.sort(ary);
			return ary[2];
		} 
         // 별도 메서드 없이 바로 가져다가 만들어도 되네
		int[] arr = new int[4];
		arr[0] = parse(n/2, r, c);
		arr[1] = parse(n/2, r, c+n/2);
		arr[2] = parse(n/2, r+n/2, c);
		arr[3] = parse(n/2, r+n/2, c+n/2);
		Arrays.sort(arr);
		return arr[2];
	}
}

---

마지막 수정일시: 2022-07-07 00:44