programmers. 쿼드압축 후 개수 세기

문제

링크

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

풀이

주어진 범위 만큼 탐색하면서 범위 안의 원소들이 같지 않다면 범위를 좌상, 좌하, 우상, 우하 총 4등분해서

4개의 범위를 다시 탐색, 반복한다

범위 내의 원소들이 같을 때 까지 반복 후 해당 원소가 0과 1인지 판단 후 각각의 값을 증가시키면 답을 구할 수 있다

첫 범위를 배열 전체를 탐색하는 범위를 주고 재귀함수를 사용하면 쉽게 구현할 수 있다

코드

    function solution(arr) {
        var answer = [0, 0];

        isAllSame([0,arr.length],[0,arr.length]);

        function isAllSame([xStart, xEnd],[yStart,yEnd]){
            let temp = arr[xStart][yStart];

            for(let i = xStart;i< xEnd;i++){
                for(let j = yStart; j<yEnd; j++) {
                    if(temp !== arr[i][j]){
                        // 좌상
                        isAllSame([xStart, (xStart+xEnd)/2], [yStart, (yStart+yEnd)/2]);
                        // 우상
                        isAllSame([xStart, (xStart+xEnd)/2], [(yStart+yEnd)/2, yEnd]);
                        // 좌하
                        isAllSame([(xStart+xEnd)/2, xEnd], [yStart, (yStart+yEnd)/2]);
                        // 우하
                        isAllSame([(xStart+xEnd)/2, xEnd], [(yStart+yEnd)/2, yEnd]);
                        return ;
                    }
                }
            }
            (temp === 0) ? answer[0]++ : answer[1]++;
        }

        console.log(answer);
        return answer;
    }