[Java] 백준 17829번 : 222-풀링

문제

조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 222-풀링이라 부르기로 했다.

다음은 8×8 행렬이 주어졌다고 가정했을 때 222-풀링을 1회 적용하는 과정을 설명한 것이다

1. 행렬을 2×2 정사각형으로 나눈다.
2. 
3. 각 정사각형에서 2번째로 큰 수만 남긴다. 여기서 2번째로 큰 수란, 정사각형의 네 원소를 크기순으로 a4 ≤ a3 ≤ a2 ≤ a1 라 했을 때, 원소 a2를 뜻한다.
4. 
5. 2번 과정에 의해 행렬의 크기가 줄어들게 된다.

종욱이는 N×N 행렬에 222-풀링을 반복해서 적용하여 크기를 1×1로 만들었을 때 어떤 값이 남아있을지 궁금해한다.

랩실 활동에 치여 삶이 사라진 종욱이를 애도하며 종욱이의 궁금증을 대신 해결해주자.

입력

첫째 줄에 N(2 ≤ N ≤ 1024)이 주어진다. N은 항상 2의 거듭제곱 꼴이다. (N=2K, 1 ≤ K ≤ 10)

다음 N개의 줄마다 각 행의 원소 N개가 차례대로 주어진다. 행렬의 모든 성분은 -10,000 이상 10,000 이하의 정수이다. 

출력

마지막에 남은 수를 출력한다.

예제 입력 1

4
-6 -8 7 -4
-5 -5 14 11
11 11 -1 -1
4 9 -2 -4

예제 출력 1

11

예제 입력 2

8
-1 2 14 7 4 -5 8 9
10 6 23 2 -1 -1 7 11
9 3 5 -2 4 4 6 6
7 15 0 8 21 20 6 6
19 8 12 -8 4 5 2 9
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24

예제 출력 2

17

힌트

예제2는 본문에 이어 다음과 같은 과정으로 답을 구할 수 있다.

 

소스코드

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

public class Main {

	private static BufferedReader bf;
	private static StringTokenizer st;
	
	private static int N;
	private static int [][] map, newMap;
	private static List<Integer> list;
	
	public static void main(String[] args) throws NumberFormatException, IOException {

		bf=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(bf.readLine());
		map=new int[N][N];
		
		for(int r=0;r<N;r++) {
			st=new StringTokenizer(bf.readLine());
			for(int c=0;c<N;c++) {
				map[r][c]=Integer.parseInt(st.nextToken());
			}
		}
		
		int size=N;
		while(size>1) {	// 원소가 1개 남을 때까지 222풀링을 진행함
			list=new ArrayList<>();	// 크기를 절반으로 줄일 때 남게되는 원소들을 저장할 리스트
			for(int r=0;r<size;r+=2) {	// 행렬을 2x2 정사각형으로 나누어 2번째로 큰 수를 찾으러 감
				for(int c=0;c<size;c+=2) {
					list.add(find(r, c));
				}
			}
			size/=2;	// 2번째로 큰 수들을 모두 찾은 후에 행렬의 크기를 절반으로 줄임
			
			map=new int[size][size];
			map=makeMatrix(size);	// 절반으로 줄어든 새로운 행렬을 map에 저장함
		}
		System.out.println(map[0][0]);
	}

	public static int find(int x, int y) {	// 2x2 정사각형에서 2번째로 큰 수를 찾는 메서드
		int first=Integer.MIN_VALUE, second=Integer.MIN_VALUE;
		for(int r=0;r<2;r++) {
			for(int c=0;c<2;c++) {
				if(map[x+r][y+c]>first) {
					second=first;
					first=map[x+r][y+c];
				} else if(map[x+r][y+c]>second) {
					second=map[x+r][y+c];
				}
			}
		}
		return second;
	}
	
	public static int[][] makeMatrix(int size) {	// 크기가 절반으로 줄어든 새로운 행렬 만들기
		newMap=new int[size][size];
		int idx=0;
		for(int r=0;r<size;r++) {
			for(int c=0;c<size;c++) {
				newMap[r][c]=list.get(idx++);
			}
		}
		return newMap;
	}
}