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

Kyle·2021년 1월 5일

Problem Solving 쿼드압축 후 개수 세기 프로그래머스

problem solving

목록 보기

27/36

쿼드압축 후 개수 세기

문제

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

위 그림과 같이 배열을 압축해 0과 1을 개수를 배열로 반환하는 문제

해결방법

재귀로 해결했다. 가장 큰 배열을 입력받고, 그 배열을 4등분 하면서 check해야되기 때문에 재귀를 이용하면 되겠다라고 생각했다.

종료조건이 될 때마다 인자에있는 answer(배열)에 업데이트해준다.
배열은 참조이기 때문에 재귀가 종료되고 초기 함수로 나와도 업데이트된 배열 값이 그대로 있다.

재귀 종료조건 (if문 2개)

arr(인자)의 길이가 1이면 한칸인 것이기 때문에 종료한다.
arr이 check(압축가능여부)를 통과하면 종료한다.

재귀 종료조건이 아닐때 (else)
2중 for문을 사용해서 arr을 4칸으로 나누어서 비교했다. for문의 범위 변수 i, j 를 이용해서 parseArr(arr,i,j)에서 처리해줬다.
answer에 더해주는 과정
answer가 [0의개수, 1의개수] 로 구성돼있다. 즉, 값을 인덱스로 아래와 같이 활용할 수 있다.
- arr의 길이가 1일 때 answer[arr[0]] += 1
- check가 유효할 때 answer[check(arr)] += 1

check -압축 가능 체크

주어진 배열의 전체 수의 합을 이용해서 해결했다.

총합 === 길이*길이 (전체칸의 수) 일 때 return 1
총합 === 0 return 0
else return -1

true,false가 아닌 1,0,-1로 리턴한 이유:
answer가 [0의개수, 1의개수] 로 구성돼있다.

answer[check(arr)] += 1 처럼
check함수의 반환값으로 인덱스를 지정해 더해주기위해 1,0,-1로 반환했다.

parseArr - 배열 4등분

2중 for문에서 i,j 값을 파라미터로 받아온다.
i는 row / j는 column으로 생각하고 배열을 변환해줬다.

len: 주어진 배열의 길이의 절반
len변수를 이용해서 slice를 사용해 row를 잘라주고, column도 잘라주었다.

code

변수명, 파라미터명이 친절하지 않아 주석을 많이 남겼다.

function solution(arr, answer = [0, 0]) {
  if (arr.length === 1) { //네모 한칸일 경우
    answer[arr[0]] += 1;
    return
  } else if (check(arr) >= 0) {//check 됐을경우(압축가능)
    answer[check(arr)] += 1; //check가 0,1을 리턴하기 때문에 맞는 인덱스에 1더해준다.
    return
  } else {
    for (let i = 0; i < 2; i++) {
      for (let j = 0; j < 2; j++) {
        //2중 for문을 이용해 4칸으로 나눠서 체크한다.
        solution(parseArr(arr, i, j), answer);
      }
    }
  }
  return answer;
}
//배열이 압축이 되는지 체크
//배열의 전체합과 칸의 수 비교를 통해서 판단했다.
function check(arr) {
  let cnt = 0;
  for (const x of arr) {
    cnt += x.reduce((acc, cur) => acc + cur, 0);
  }
  if (cnt === arr.length ** 2) return 1;  //1로 압축
  else if (cnt === 0) return 0; //0으로 압축
  else return -1; //아닐경우
}
//범위에 맞는 배열 parsing하기
//배열의 길이와 i,j(위의 for문에서의 i,j이다.)를 이용해서 배열 파싱
function parseArr(arr, i, j) {
  const len = arr.length / 2;
  arr = arr.slice(i * len, i * len + len);
  arr = arr.map((v) => v.slice(j * len, j * len + len));
  return arr;
}