Quard Tree (프로그래머스 레벨2, DFS, 자바스크립트 풀이)

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

 

 

문제 수준: 프로그래머스 레벨2

 

문제 요약:

이미지 압축 알고리즘으로 유명한 쿼드트리를 구현하는 문제.

문제를 읽어봤자 잘 이해는 안 가고 입출력 이미지를 봐야 이해하기 쉽다.

 

입출력 예 (입력 / 출력):

문제 풀이 전략:

반복적인 패턴이 보인다면, 늘 사용하던 dfs를 활용하면 된다.

처음 풀었을 때가 어려웠지 두 번째 비슷한 문제를 푸니까 접근 방법은 쉽게 파악이 된다.

 

내 풀이:

function solution(arr) {
    function qt(arr, leng) { // 전체 배열과 row의 갯수를 받는다.
        leng /= 2
        
        let leftUp = arr.slice(0, leng).map(line => line.slice(0, leng)) // 1사분면
        let rightUp = arr.slice(0, leng).map(line => line.slice(leng)) // 2사분면
        let leftDown = arr.slice(leng).map(line => line.slice(0, leng)) // 3사분면
        let rightDown = arr.slice(leng).map(line => line.slice(leng)) // 4사분면
        
        if (leng === 1) { // 한계조건: leng이 1이 되면 더 이상 재귀호출할 수 없고 반환한다.
            let lu = Number(leftUp) 
            let ru = Number(rightUp)
            let ld = Number(leftDown)
            let rd = Number(rightDown);
            let temp = lu + ru + ld + rd;
            
            if (temp === 0 || temp === 4) { // 모두 0이거나 4면 숫자 1개를 반환한다.
                return temp > 0 ? 1 : 0
            } else {
                return [lu, ru, ld, rd] // 통일되지 않으면 1,2,3,4분면에 각각 숫자를 담아서 반환한다.
            }
            
        }
        
        const lusum = leftUp.flat(Infinity) // 1사분면에 있는 요소들이 고차원 배열일 경우 1차원 배열로 만든다.
        const lusumReduced = lusum.reduce((a,b)=> a+b, 0)
        if (lusumReduced === lusum.length || lusumReduced === 0) { // 요소 갯수와 합이 같으면 모두 1이라는 것이고, 합이 0이면 모두 0이라는 것이다.
            leftUp = lusumReduced > 0 ? 1 : 0;
        } else {
            leftUp = qt(leftUp, leng) // 통일 되지 않은 경우 다시 재귀호출하여 될 수 있는한 쪼갠다.
        }
        const rusum = rightUp.flat(Infinity) // 2사분면에 있는 요소들이 고차원 배열일 경우 1차원 배열로 만든다.
        const rusumReduced = rusum.reduce((a,b)=> a+b, 0)
        if (rusumReduced === rusum.length || rusumReduced === 0) { // 요소 갯수와 합이 같으면 모두 1이라는 것이고, 합이 0이면 모두 0이라는 것이다.
            rightUp = rusumReduced > 0 ? 1 : 0;
        } else {
            rightUp = qt(rightUp, leng) // 통일 되지 않은 경우 다시 재귀호출하여 될 수 있는한 쪼갠다.
        }
        const ldsum = leftDown.flat(Infinity) // 3사분면에 있는 요소들이 고차원 배열일 경우 1차원 배열로 만든다.
        const ldsumReduced = ldsum.reduce((a,b)=> a+b, 0)
        if (ldsumReduced === ldsum.length || ldsumReduced === 0) { // 요소 갯수와 합이 같으면 모두 1이라는 것이고, 합이 0이면 모두 0이라는 것이다.
            leftDown = ldsumReduced > 0 ? 1 : 0;
        } else {
            leftDown = qt(leftDown, leng) // 통일 되지 않은 경우 다시 재귀호출하여 될 수 있는한 쪼갠다.
        }
        const rdsum = rightDown.flat(Infinity) // 4사분면에 있는 요소들이 고차원 배열일 경우 1차원 배열로 만든다.
        const rdsumReduced = rdsum.reduce((a,b)=> a+b, 0)
        if (rdsumReduced === rdsum.length || rdsumReduced === 0) { // 요소 갯수와 합이 같으면 모두 1이라는 것이고, 합이 0이면 모두 0이라는 것이다.
            rightDown = rdsumReduced > 0 ? 1 : 0;
        } else {
            rightDown = qt(rightDown, leng) // 통일 되지 않은 경우 다시 재귀호출하여 될 수 있는한 쪼갠다.
        }
        
        let sumAll = leftUp + rightUp + leftDown + rightDown; // 혹시 모두 0 혹은 1일 경우 자연수가 된다.
        if (sumAll === 4 || sumAll === 0) { // 자연수 4이거나 0이라면(모두 1이거나 0이라면)
            return sumAll > 0 ? 1 : 0 // 1혹은 0을 반환하고 함수 종료.
        }
        return [leftUp, rightUp, leftDown, rightDown] // 합이 숫자가 아닌경우 배열들인 것으므로 1,2,3,4분면에 맞춰서 반환한다.
    }
    
    // 아래부터는 함수 실행 로직
    let leng = arr.length; 
    
    if (leng === 1) { // input값 n = 1인 경우
        return arr.flat(Infinity)[0] > 0 ? [0, 1] : [1, 0]
    } else { // input값 n이 2 이상인 경우
        let ans = qt(arr, leng) // 함수 함 돌리고
        if (isNaN(ans)) { // 모든 숫자가 1이거나 0이 아니라면
            ans = ans.flat(Infinity)
            let zeroSum = 0;
            let oneSum = 0;

            ans.forEach(val => {
                if (val === 0) {
                    zeroSum++
                } else {
                    oneSum++
                }
            })
            return [zeroSum, oneSum]
        } else { // 모든 숫자가 1이거나 0인 기적이 있었다면
            return ans > 0 ? [0, 1] : [1, 0]
        }
    }
}

 

 

백준 골드5 달고 나서는 전혀 코테를 진행하지 않고, 프로젝트 진행과 리팩토링에만 신경쓰고 있었다.

그러다가 오늘 오랜만의 코테 solve를 진행했다. 감 떨어지지 않게 2~3일에 1문제는 풀어야지..

 

예전에 풀었던 쿼드 트리와 비슷한 문제를 풀었다.

대충 로직은 맞지만 return하는 부분을 조금 지저분하게 짠거 같다. 2시간 좀 넘게 걸린듯..