[BOJ / Node.js] 17829 222-풀링

https://www.acmicpc.net/problem/17829

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

 

Solve

• 문제를 읽고 고민한 부분은 2번째로 큰 수를 반환하는 함수 만들기와 2 x 2 행렬로 줄여나가는 함수 만들기 입니다.
• 문제에서 정의한 2번째로 큰 수는 원소를 크기 순으로 나열했을 때, 두 번째에 있는 원소이므로, findSecondNumber 함수를 만들어 주었습니다.
• 반복적으로 행렬을 1/2씩 줄여나가야 하기 때문에 base case를 행렬 크기인 n이 1인 경우로 설정하였고, 이중 for문을 통해 2 x 2 행렬에 해당하는 원소들을 비교하여 2번째로 큰 수를 배열에 담아 새로운 행렬을 만들어 주었습니다.

Code

const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");

const n = +input.shift();
const arr = input.map(el=>el.split(' ').map(el=>+el));

const findSecondNumber = (arr) => {
    arr.sort((a,b)=>b-a);
    return arr[1]
}


const polling = (n,matrix) => {

    if(matrix.length === 1) return matrix[0][0];
    const newMatrix = [];
    for(let i = 0 ; i < n; i+=2) {
        const temp = [];
        for(let j =0 ; j <n; j+=2) {
            temp.push(findSecondNumber([matrix[i][j], matrix[i+1][j], matrix[i][j+1], matrix[i+1][j+1]]));
        }
        newMatrix.push(temp);
    }
    return polling(n/2,newMatrix)
}

console.log(polling(n, arr));