[프로그래머스] 쿼드 압축 후 개수 세기 - 자바스크립트

문제

코딩테스트 연습 - 쿼드압축 후 개수 세기

 

코드

function solution(arr) {
    if(arr.length === 1) return arr[0][0] ? [0,1] : [1,0];
    const answer = [0,0];
    const len = arr.length;
    const half = len / 2;

    const number = arr[0][0];
    let flag = true;

    out:for(let i=0; i<len; i++){
        for(let j=0; j<len; j++){
            if(number !== arr[i][j]){
                flag = false;
                break out;
            }
        }
    }
    if(flag){
    	answer[number]++;
        return answer;
    }

    for(let i=0; i<2; i++){
        for(let j=0; j<2; j++){
            const compressArr = [];
            for(let k=0; k<half; k++){
                compressArr.push(arr[(half * i) + k].slice(j * half, (j+1) * half));
            }
            const [zero, one] = solution(compressArr);
            answer[0]+=zero;
            answer[1]+=one;
        }
    }
    return answer;
}

 

풀이

간단히 흐름만 파악하고, 코드 라인에 주석으로 설명을 대체했다.

 

2차원 정수 배열 arr을 쿼드 트리 방식으로 압축한다.

압축 절차는 arr 배열을 서로 겹치지 않는 가장 큰 4개의 정사각형이 되도록 나눠간다.

 

 

문제에 제시된 이 그림의 절차대로 코드를 작성했다.

 

정사각행렬의 크기가 1일 때 까지 나눠줘야 한다.

 

문제 풀이에는 여러 방법이 있겠지만, 위 절차를 구현하기 위해 재귀함수를 이용했다.

 

주석을 포함한 코드

function solution(arr) {
    if(arr.length === 1) return arr[0][0] ? [0,1] : [1,0]; // 배열 크기가 1이면 값에 따라 0,1 개수 반환
    const answer = [0,0]; // 각 절차마다 반환을 위한 정답 배열
    const len = arr.length;
    const half = len / 2; // 정사각행렬 arr를 총 4개의 가장 큰 정사각형으로 나눠야 하기 때문에 절반 값을 취한다.

    const number = arr[0][0]; // 현재 재귀단계에서, 모든 행렬 구성 값이 같다면 하나로 압축해줄 수 있을 것.
    let flag = true; // 행렬의 구성 값이 모두 같지 않다면, 빠르게 반복문을 탈출. flag 변수로 행렬 구성 상태를 파악한다.

    out:for(let i=0; i<len; i++){
        for(let j=0; j<len; j++){
            if(number !== arr[i][j]){ // 행렬의 구성 값이 통일되지 않았다면 즉시 바깥(out) for문을 종료시킨다.
                flag = false;
                break out;
            }
        }
    }
    if(flag){
    	answer[number]++;
        return answer;
    } // 행렬의 구성 값이 모두 같다면 number 값에 따라 0,1 개수 반환

      // 아래의 코드는 행렬의 구성 값이 통일되지 않았을 때 진행된다.
    for(let i=0; i<2; i++){
        for(let j=0; j<2; j++){
            const compressArr = []; // 압축을 위해 다음 재귀에 넣어줄 행렬을 선언.
            for(let k=0; k<half; k++){
                compressArr.push(arr[(half * i) + k].slice(j * half, (j+1) * half));
            } // i,j값이 변할 때 arr을 구성하는 가장 큰 정사각행렬의 값을 구하는데, 총 i*j = 4로 4개를 구한다.
            const [zero, one] = solution(compressArr); 
              // 4개의 정사각행렬을 각각 다음 재귀로 넣어주고, 반환 값을 [zero, one] 변수에 담아서 answer 배열에 넣어준다.
            answer[0]+=zero;
            answer[1]+=one;
        }
    }
    return answer;
    // 행렬의 구성 값이 통일되지 않았을 때는 각 재귀마다 answer를 반환한다.
      // 가장 큰 정사각행렬의 return문이 맨 마지막에 실행되므로 [zero,one] 값을 모두 더한 값이 반환된다.

 

다음의 코드의 동작 순서를 이해하기 위해서는, 콜스택을 이해해야 한다.

 

가장 먼저 실행된 재귀는 입력으로 주어진 arr 배열을 처리하는 절차이며,

가장 나중에 끝나는 재귀 역시 맨 처음 입력으로 주어진 arr 배열에서의 절차이므로 정답을 구할 수 있다.