[프로그래머스] 쿼드압축 후 개수 세기 (JS)

hhkim·2023년 10월 4일
0

Algorithm - JavaScript

목록 보기
150/188
post-thumbnail

풀이 과정

재귀
1. 현재 영역의 모든 요소가 같은지 확인
2. 모두 같으면 0 또는 1의 결과 개수 +1하고 재귀 빠져나오기
3. 아니면 4 구역으로 나눠서 재귀

코드

function solution(arr) {
  const result = [0, 0];
  const recursion = (hs, he, ws, we) => {
    const tmp = arr[hs][ws];
    let flag = true;
    for (let i = hs; i < he; ++i) {
      for (let j = ws; j < we; ++j) {
        if (tmp !== arr[i][j]) {
          flag = false;
          break;
        }
      }
      if (!flag) break;
    }
    if (flag) {
      ++result[tmp];
      return;
    }
    const nh = hs + (he - hs) / 2;
    const nw = ws + (we - ws) / 2;
    recursion(hs, nh, ws, nw);
    recursion(hs, nh, nw, we);
    recursion(nh, he, ws, nw);
    recursion(nh, he, nw, we);
  };
  recursion(0, arr.length, 0, arr.length);
  return result;
}

🦾

그림 보자마자 재귀다 하는 느낌이 왔다.
문제는 재귀 실행할 때 전달하는 인자 값을 잘못 줘서 자꾸 콜스택 초과 오류가 나는 바람에 디버깅하느라 시간을 한참 썼다.
그래도 1시간 안에 해결돼서 기분이 좋다.

0개의 댓글