[Programmers] 쿼드압축 후 개수 세기

문제

 

월간 코드 챌린지 시즌1 > 쿼드압축 후 개수 세기

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

 

 

아이디어

 

이번 문제의 아이디어는 DFS입니다.

 

원하는 조건이 달성되지 않으면 달성될 때까지 깊이를 최대한 들어가면서 탐색해주면 됩니다.

 

풀이법은 생각보다 간단합니다.

 

1. 배열 전체를 탐색

2. 모든 배열 값이 동일하지 않다면 현재 배열을 기준으로 4등분을 한 뒤 분할된 배열들을 1부터 다시 시작

3. 모든 배열값이 동일하다면 배열 값에 대해 개수 카운트 하기

 

 

구현 코드 (JavaScript)

 

const res = [0, 0];

const solve = (startI, endI, startJ, endJ, arr) => {
    let val = -1;

    // 범위내에 있는 모든 배열 값들이 동일한지 확인
    for(let i=startI; i<=endI; i++) {
        for(let j=startJ; j<=endJ; j++) {
            if(val === -1) {
                val = arr[i][j]; // 초기 배열에 담겨있는 값 저장
            } else if(val !== arr[i][j]) { 
                solve(startI, Math.floor((startI + endI)/2), startJ, Math.floor((startJ + endJ)/2), arr); // 좌상단
                solve(startI, Math.floor((startI + endI)/2), Math.floor((startJ + endJ)/2)+1, endJ, arr); // 우상단
                solve(Math.floor((startI + endI)/2)+1, endI, startJ, Math.floor((startJ + endJ)/2), arr); // 좌하단
                solve(Math.floor((startI + endI)/2)+1, endI, Math.floor((startJ + endJ)/2)+1, endJ, arr); // 우하단

                return;
            }
        }
    }

    // 값이 모두 동일한 경우 val값에 대한 count 증가
    res[val]++;
}

function solution(arr) {
    solve(0, arr.length-1, 0, arr.length-1, arr);

    return res;
}

 

 

읽어주셔서 감사합니다.