Programmers / Level 2 / 쿼드압축 후 개수 세기 / JS

문제 간단설명

0과 1로만 이루어진 2차원 배열 arr가 주어진다.

특정 영역내에 모두 0 또는 1로 되어있다면 하나로 압축한다.

그렇지 않다면, 4개의 균일한 정사각형 영역으로 쪼갠 뒤, 위와 같이 압축한다.

위 과정을 끝까지 반복했을 시에 0과 1의 개수가 몇개인지 반환하는 문제이다.

 

제한 사항

• arr의 행의 개수는 1이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다.
  • arr는 정사각형 배열이다.
  • arr의 각 행에 있는 모든 값은 0 또는 1이다.

 

성공 코드

function solution(arr) {
  let zeroCount = 0;
  let oneCount = 0;

  /**
   * 영역내에 인자로 받은 number와 모두 같은 값인지 판단하는 함수이다.
   *
   * @param {number} startRow 시작 행
   * @param {number} startCol 시작 열
   * @param {number} count 행 혹은 열의 개수
   * @param {number} number 기준 값
   * @returns 모두 같은 값인지 boolean 값으로 반환한다.
   */
  const isAllSame = (startRow, startCol, count, number) => {
    for (let i = startRow; i < startRow + count; i++) {
      for (let j = startCol; j < startCol + count; j++) {
        if (arr[i][j] !== number) {
          return false;
        }
      }
    }

    return true;
  };

  /**
   * 쿼드 압축을 수행하는 함수
   *
   * @param {number} startRow 시작 행
   * @param {number} startCol 시작 열
   * @param {number} count 행 혹은 열의 개수
   */
  const quadZip = (startRow, startCol, count) => {
    // 현재 영역내에 모든 값이 0이라면 1개의 0으로 압축한다.
    if (isAllSame(startRow, startCol, count, 0)) {
      zeroCount++;
      return;
    }
    // 현재 영역내에 모든 값이 1이라면 1개의 1로 압축한다.
    if (isAllSame(startRow, startCol, count, 1)) {
      oneCount++;
      return;
    }

    // 현재 2 * 2의 배열이라면, 더 이상 압축할 수 없으므로 개수를 모두 세준다.
    if (count === 2) {
      for (let i = startRow; i < startRow + count; i++) {
        for (let j = startCol; j < startCol + count; j++) {
          if (arr[i][j] === 0) {
            zeroCount++;
          } else {
            oneCount++;
          }
        }
      }

      return;
    }

    // 위에서 압축할 수 없는 값이거나, 2 * 2 보다 큰 배열일 경우 4등분하여 쿼드 압축을 진행한다.
    quadZip(startRow, startCol, count / 2);
    quadZip(startRow, startCol + count / 2, count / 2);
    quadZip(startRow + count / 2, startCol, count / 2);
    quadZip(startRow + count / 2, startCol + count / 2, count / 2);
  };

  quadZip(0, 0, arr.length);

  return [zeroCount, oneCount];
}

 

문제에 나와있는 그대로 풀이한 방법이다. 처음에는 특정 영역 내에 모두가 0인지 1인지 검사하는 함수를 따로 나누어서 작성했다. 하지만 로직이 똑같기 때문에, 인자를 하나 추가해서 그 인자로 0 또는 1을 받아서 그 인자와 모두 같은 값인지 체크할 수 있도록 하나의 함수로 작성했다.

 

그리고 쿼드압축 부분은 재귀로 작성했다.

문제 그대로 코드를 작성했지만, 다른 사람들의 풀이와 달리 배열을 새로 만들거나 배열을 조작하지는 않았다.

문제가 '압축'이라고 표현되어있지만, 답은 단순히 0의 개수와 1의 개수이기 때문에 영역내에 모두 값이 같다면 단순히 결과에 카운트 1만 늘려주면 되는 문제였다.

 

4등분해서 나누어서 생각했을 때, 인덱스 관련 부분만 조심하면 크게 틀릴 것이 없는 문제였다.