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

 

 

난이도: Lv. 2

정답률: 53%

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

프로그래머스

 

 

알고리즘

BFS를 사용하여 문제를 푼다. 큐에는 압축하고자 하는 특정 영역의 [시작 행, 시작 열, 마지막 행, 마지막 열]을 저장한다.

1. 큐에 압축하고자 하는 특정 영역의 배열을 push() 한다.

2. 해당하는 영역 내부에 있는 모든 수가 같은지 확인한다.

2-1. 같은 경우 정답 배열의 해당 값을 증가시킨다.

2-2. 같지 않은 경우 영역을 정사각형으로 4등분하여 큐에 push() 한다.

 

 

코드

function solution(arr) {
    const answer = [0, 0];
    let queue = [[0, 0, arr.length - 1, arr.length - 1]];

    while (queue.length) {
        const shiftArr = queue.pop();
        const num = arr[shiftArr[0]][shiftArr[1]];
        let isAllSame = true;

        for (let i = shiftArr[0]; isAllSame && i <= shiftArr[2]; i++) {
            for (let j = shiftArr[1]; j <= shiftArr[3]; j++) {
                if (arr[i][j] !== num) {
                    isAllSame = false;

                    const floorRow = Math.floor((shiftArr[0] + shiftArr[2]) / 2);
                    const ceilRow = Math.ceil((shiftArr[0] + shiftArr[2]) / 2);
                    const floorCol = Math.floor((shiftArr[1] + shiftArr[3]) / 2);
                    const ceilCol = Math.ceil((shiftArr[1] + shiftArr[3]) / 2);

                    queue.push([shiftArr[0], shiftArr[1], floorRow, floorCol]);
                    queue.push([shiftArr[0], ceilCol, floorRow, shiftArr[3]]);
                    queue.push([ceilRow, shiftArr[1], shiftArr[2], floorCol]);
                    queue.push([ceilRow, ceilCol, shiftArr[2], shiftArr[3]]);

                    break;
                }
            }
        }

        if (isAllSame) { answer[num]++; }
    }

    return answer;
}

 

 

주저리

다른 언어도 그런지는 모르겠지만 js는 shift()보다 pop()을 쓰는 게 훨씬 빠르다. 처음에 shift()로 풀었는데 테케 5번이 시간초과 나서 다른 부분에서 시간을 줄여봤는데 그래도 통과가 되지 않았다. shift() 대신 pop()을 쓰니까 통과됐다. 이름은 queue라고 지어놨는데 사실상 stack이다.