문제설명

0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

1. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

---

제한사항

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

---

입출력 예

arr	result
[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]]	[4,9]
[[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]]	[10,15]

---

입출력 예 설명

입출력 예 #1

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.
• 
• 최종 압축 결과에 0이 4개, 1이 9개 있으므로, [4,9]를 return 해야 합니다.

입출력 예 #2

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.
• 
• 최종 압축 결과에 0이 10개, 1이 15개 있으므로, [10,15]를 return 해야 합니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

설계 과정

• 우선 1과 0의 개수를 세줄 answer 배열 [0,0]을 생성해두자.

1. answer을 substr을 이용하기 용이하기 위해 문자열로 변경
2. len 변수 초기값은 가로 한줄로 지정
3. len만큼 문자열을 가로세로로 잘라냄.
4. 그 잘라낸 값이 모두 같은 값인지 체크 (첫번째 요소랑 같은지 확인하면 좋을듯)
5. 모두 같다면 그 부분을 임의의 값 2로 변경 그리고 같은 값 answer인덱스 부분에 +1을 해줌.
6. len 부분을 나누기 2해주면서 len이 1보다 작아질때까지 위에 과정 반복
7. 마지막에 남은거에서 1과 0을 찾아서 answer을 통해 개수 세줌.

정답 코드

//문자열 값 변경을 위한 함수
String.prototype.replaceAt = function(index, replacement) {
    if (index >= this.length) {
        return this.valueOf();
    }
 
    return this.substring(0, index) + replacement + this.substring(index + 1);
}

function solution(arr) {
    var answer = [0,0];
    const regex = /["0""1"]/g
    for(var i = 0;i<arr.length;i++){
        arr[i] = arr[i].join("");
    }
    //4
    var len = arr.length;
    var checkNum ="";
    while(true){
        //0 -> 4
        for(var i = 0;i<arr.length;i+=len){
            for(var k = 0;k<arr.length;k+=len){
                checkNum ="";
                if(arr[i][k]!=='0'&&arr[i][k]!=='1') continue;
                for(var l = 0;l<len;l++){
                    checkNum+=(arr[i+l].substr(k,len));
                }
              
                // 모두 같은 건지 체크
                for(var checkI=1;checkI<checkNum.length;checkI++){
                    if(checkNum[checkI] !== checkNum[0] ){
                        break;
                    }
                    //모두 같다면
                    if(checkI === checkNum.length-1){
                        answer[checkNum[0]]++;
                        //값 치환
                        for(var l = 0;l<len;l++){
                            for(var eraseI = k; eraseI<k+len;eraseI++){
                                arr[i+l] =arr[i+l].replaceAt(eraseI,"2");
                            }
                            
                        }
                    }

                }
                
            }
        }
        len = len/2;
        if(len<1) break;
    }
    
    //마지막 1한개 남은거 체크
    for(var i = 0;i<arr.length;i++){
        for(var k = 0;k<arr[i].length;k++){
            if(arr[i][k]==='0'||arr[i][k]==='1'){
                answer[arr[i][k]]++;
            }
        }
    }
    return answer;
}

결과

조금씩 설계대로 잘 안되는 부분이 있어서 코드가 생각보다 길어진 감이 있다. 설계를 좀 더 자세히 진행하여 이러한 상황을 줄이는 것이 좋을 것 같다.