[JS] 쿼드압축 후 개수 세기 (2차원 배열 복사)

문제

처음 풀이 (오답 -> 시간초과)

function solution(arr) {
    const answer = [0, 0];
    let len = arr.length;
    let newArr = [...arr];
    
    function bfs(y, x, r) {
        const origin = newArr[y][x];
        let temp = JSON.parse(JSON.stringify(newArr));
        
        for (let row = y; row < y + r; row++) {
            for (let column = x; column < x + r; column++) {
                if (newArr[row][column] === origin) {
                    temp[row][column] = -1;
                } else {
                    return false;
                }
            }
        };
        
        answer[origin] = answer[origin] + 1;
        newArr = JSON.parse(JSON.stringify(temp));
        return true;
    };
    
    if (bfs(0, 0, len)) {
        return answer;
    };
    
    len = len / 2;
    
    while (len >= 1) {
        for (let row = 0; row < arr.length; row = row + len) {
            for (let column = 0; column < arr.length; column = column + len) {
                if (newArr[row][column] !== -1) {
                    bfs(row, column, len);
                }
            }
        };
        len = len / 2;
    };
    return answer;
}

최대한 문제에서 소개된 순서대로 풀었습니다.
테스트 케이스도 맞고 이론상 풀리긴하지만 시간 초과가 발생했습니다.
아마 2차원 배열을 계속 복사하고 반복해서 같은 곳을 반복해서 그렇다고 생각이 됩니다.

문제를 풀면서 다시 한번 배운 것이 있는데 2차원 배열 복사에 관련한 내용입니다.

보통 배열 복사를 할 때, 다음과 같은 방법을 사용합니다.
참고

• Spread 연산자( ... ) - 얕은 복사
• map() 함수 - 얕은 복사
• filter() 함수 - 얕은 복사
• reduce() 함수 - 얕은 복사
• slice() 함수 - 얕은 복사
• from() 함수 - 얕은 복사

하지만 위와 같은 경우는 다차원 배열을 제대로 복사하지 못하는 문제가 생깁니다. 그래서 다차원 배열을 복사할 때에는

"JSON.parse() 함수 및 JSON.stringify() 함수 - 깊은 복사"

방법을 사용하게 됩니다.

위 코드에서도
newArr = JSON.parse(JSON.stringify(temp));
처럼 사용했습니다.

정답 풀이

function solution(arr) {
    var answer = [0, 0];
    
    function check(row, column, n) {
        let flag = true;
        for (let y = row; y < row + n; y++) {
            for (let x = column; x < column + n; x++) {
                if (arr[row][column] !== arr[y][x]) {
                    flag = false;
                    break;
                }
            };
        };
        if (flag) return answer[arr[row][column]]++;
        else {
            check(row, column, n / 2);
            check(row + n / 2, column, n / 2);
            check(row, column + n / 2, n / 2);
            check(row + n / 2, column + n / 2, n / 2);
        }
    }
    
    check(0, 0, arr.length);
    
    return answer;
}

문제를 풀고 난 뒤에는 굳이 배열을 복사할 필요가 있었나라는 생각이 들었습니다. 문제를 푸는 아이디어는 다음과 같습니다.

• 좌표 0, 0을 기준으로 배열 크기만큼 순회 하면서 값이 같은지 비교합니다. arr[row][column] !== arr[y][x]
• 만약에 값이 다르다면 flag를 false로 바꾸고 바로 for문을 종료합니다.
• 값이 다르지 않다면 answer의 값을 1올려주고 return해줍니다.
• 다르다면 현재 크기에서 나누기 2를 한 부분들의좌표 값들과 크기를 재귀해줍니다.