(프로그래머스 JS)쿼드압축 후 개수 세기

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

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

분할 정복 알고리즘 적용.

 

check 함수를 이용해 분할을 할지 결정한다.

check의 시작은 출발좌표인 0, 0과 arr의 길이를 넘겨주도록 한다.

 

check 함수.

분할 조건은 sx, sy에서 시작해서 length까지의 수가 모두 같지 않을 때다.

이중 for문을 이용해서 이를 확인하도록 한다.

만약 수가 같지 않았을 경우 check()함수로 분할을 진행한다.

 

분할은 4 부분으로 나누면 되기 때문에 x, y 좌표와 분할 범위를 적절하게 넘겨주면 된다.

function solution(arr) {
    const answer = [0, 0];
    const m = arr.length;
    
    const check = (sx, sy, length) => {
        const first = arr[sx][sy];
        const half = Math.floor(length / 2);
        
        for(let i = sx; i < sx + length; i++){
            for(let j = sy; j < sy + length; j++){
                if(arr[i][j] !== first){
                    check(sx, sy, half);
                    check(sx + half, sy, half);
                    check(sx, sy + half, half);
                    check(sx + half, sy + half, half);
                    
                    return;
                }
            }
        }
        
        answer[first]++;
    }
    
    check(0, 0, m);
    
    return answer;
}