[CodeKata] 프로그래머스 : 3.1(월), 쿼드압축 후 개수

🥋 Ooooth!! (Level 2)

 

🧮 풀이

function solution(arr) {
  let l = arr.length;
  const count = arr.flat().filter(e => e === 0).length;
  let answer = {
    0: count,
    1: l*l - count,
  };
  let check = Array.from({length: l}, () => Array.from({length: l}, () => false))
  while (l > 2) {
    for (let i = 0 ; i < arr.length ; i += l/2) {
      for (let j = 0 ; j < arr.length ; j += l/2) {
        const quadBox = arr.slice(i, i+l/2).map(e => e.slice(j, j+l/2)).flat();
        if (check[i][j] === false && quadBox.every(e => e === quadBox[0])) {
          for (let m = i ; m < i+l/2 ; m++) {
            for (let n = j ; n < j+l/2 ; n++) {
              check[m][n] = true;
            }
          }
          answer[quadBox[0]] -= (quadBox.length - 1)
        }
      }
    }
    l /= 2;
  }
  return Object.values(answer);
}

1. l은 arr의 길이이자, 우리가 2씩 나누는 것을 반복할 때 기준값이 된다. answer는 0, 1의 개수배열로 처음엔 모든 개수를 넣어준다.
2. check는 쿼드압축 진행여부를 저장하는 배열이다. arr와 같은 크기의 이차원 배열로 만들며, 값은 false로 초기화한다.
3. while 반복문을 반복한다. 안에는 이차원 배열(arr)을 순회하는데, 인덱스는 l/2씩 증가시킨다. (박스 쿼드등분)
4. quadBox는 현재 인덱스(i, j)에서 slice()한 단위 쿼드박스이다. 이를, flat() 처리하면 일차원 배열 형태로 가공할 수 있다.
5. check가 false고, quadBox 모든 값이 같다면 이는 압축이 가능하다는 의미이다. 해당 단위 쿼드박스의 check는 true로 바꿔준다.
6.  quadBox[0]은 0 혹은 1이자 현재 quadBox의 모든 값일 것이다. 이를 하나로 합친다면, answer 개수를 (quadBox.length - 1) 만큼 빼줘야 한다.
7. while 반복문이 돌 수 있도록, 마지막에 l을 2로 나누고 반복한다. 종료조건은, l = 2(쿼드박스 길이가 1일 때) 이다.

 

🖇 리뷰

내 풀이에서 테스트 10번을 통과할 수 없었다. 모범답안을 검색했고, 재귀함수 패턴을 사용했어야 하는 문제였다.

function quad(array, size, countArray, start) {
    const first = array[start[0]][start[1]]; // 시작 지점의 값
    if(size === 1) { // size가 1이면 마지막이다. first 값에 따라서 countArray의 값을 증가시켜준다.
        first === 0 ? countArray[0] += 1 : countArray[1] += 1;
        return;
    }
    
    const half = size / 2; // 정사각형의 절반 가로, 세로 동일
    let keep = true;
    
    for (let i = start[0]; i < start[0] + size; i++) {
        for(let j = start[1]; j < start[1] + size; j++) { // 모든 값이 다 같은지 확인한다. 하나라도 다르면 keep을 false로 변경
            if(first !== array[i][j]) {
                keep = false;
                break;
            }
        }
        if(!keep) break;
    }
    // keep이 true일 경우 모두가 다 같다는 뜻이므로, 하나만 확인하여 증가시켜 주면 된다. 그리고 안에 더 확인할 필요가 없으니 return
    if(keep) {
        first === 0 ? countArray[0]++ : countArray[1]++ ;
        return;
    }
    // keep이 false 일 경우 4등분하여 다시 해주면 된다.
    quad(array, half, countArray, start);
    quad(array, half, countArray, [start[0], start[1]+half]);
    quad(array, half, countArray, [start[0] + half, start[1]]);
    quad(array, half, countArray, [start[0] + half, start[1] + half]);
    return;
}

function solution(arr) {
    const countArray = [0, 0];
    const size = arr.length;
    quad(arr, size, countArray, [0, 0]);
    return countArray;
}

* 출처 : velog.io/@ansrjsdn/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Level2-%EC%BF%BC%EB%93%9C-%EC%95%95%EC%B6%95-%ED%9B%84-%EA%B0%9C%EC%88%98-%EC%84%B8%EA%B8%B0-javascript

 

quad() 라는 쿼드박스 확인함수를 만든다. 인자는, array(초기배열), size(쿼드박스 길이), countArray(정답), start(시작점) 4개.

size가 1이라면 마지막 쿼드박스이므로, countArray의 0 혹은 1의 개수를 증가시킨다.

아니라면, size를 우선 2로 나눈다.(half) keep과 이중 for문은 해당 쿼드박스의 모든 값이 같은지 확인하는 로직이다.

같지 않다면 keep = false, 모두 같다면 keep = true와 countArray 개수증가를 진행한다. 

마지막으로, 재귀함수를 4회 진행한다. 각각에는, size에 half 할당과, start 시작점을 4등분한 첫 지점으로 잡아준다.

 

재귀함수가 로직이 길어보여도, 내가 만든 while문, for문(사실상 4중..)에 비해 훨씬 빠른 속도를 보이는 것 같았다.

모든 값의 비교는, 위 이중for문보다는 내가 했던 flat() 후 every() 조합이 더 유용하다고 생각된다.