[프로그래머스] 쿼드압축 후 개수 세기

https://programmers.co.kr/learn/courses/30/lessons/68936

문제 설명

0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

1. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

나의 풀이

const subset = (arr) => {
    if (arr.length < 2) return arr;

    const first = arr.slice(0, arr.length/2).map((item) => item.slice(0,arr.length/2));
    const second = arr.slice(0, arr.length/2).map((item) => item.slice(arr.length/2,arr.length));
    const third = arr.slice(arr.length/2, arr.length).map((item) => item.slice(0,arr.length/2));
    const forth = arr.slice(arr.length/2, arr.length).map((item) => item.slice(arr.length/2,arr.length));

    return [first, second, third, forth];
};

const check = (arr) => {
    const number = arr[0][0];

    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length; j++) {
            if (arr[i][j] !== number) return false;
        }
    }
    return true;
}

function solution(arr) {  

    if (check(arr)) {
        if (arr[0][0] === 0) return [1, 0]; 
        if (arr[0][0] === 1) return [0, 1]; 
    }

    const answer = subset(arr).reduce((acc, curr) => {
        const [zeroNum, oneNum] = solution(curr);

        return [acc[0]+zeroNum, acc[1]+oneNum];
    }, [0,0])

    return answer;
}

문제 회고

일단 문제를 보고 2차원 배열을 각각 네 부분으로 나눠 가면서 모두 다 똑같은 숫자인지 체크를 하고 아니면 다시 네 부분으로 나누고 이런 방식으로 돌아간다는 것을 알았다.

처음에는 그래서 startX, startY라는 변수를 두고 체크하는 함수를 만들어야겠다는 생각을 했다. 그런데 문제를 보다보니 네 부분으로 나눈 뒤에 각 부분에 돌아가는 기능이 똑같으니 재귀함수를 이용하는 것이 어떨까 하는 생각이 들었다.

그런데 재귀함수로 이용하기 위해서는 각 배열의 각 부분을 각각의 완전한 배열로 뽑아내는 것이 중요했다. 그래서 만든 함수가 subset()이라는 함수이다.

const subset = (arr) => {
    if (arr.length < 2) return arr;

    const first = arr.slice(0, arr.length/2).map((item) => item.slice(0,arr.length/2));
    const second = arr.slice(0, arr.length/2).map((item) => item.slice(arr.length/2,arr.length));
    const third = arr.slice(arr.length/2, arr.length).map((item) => item.slice(0,arr.length/2));
    const forth = arr.slice(arr.length/2, arr.length).map((item) => item.slice(arr.length/2,arr.length));

    return [first, second, third, forth];
};

그리고 나서 solution()에서 매개변수로 들어온 배열이 모두 똑같은 수로 되어 있는지 체크를 하고 만약 아니라면 4개의 부분으로 나눠서 다시 재귀함수를 돌린 다음 각각 재귀함수로 돌린 결과를 더해주었다.

뭔가 깔끔하게 푼 것 같아서 마음에 든다.