[TIL #20] 쿼드압축 후 개수 세기

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

프로그래머스

 

쿼드압축도 몰랐고, 쿼드트리도 처음 봤다.

뭔데 이게...

일단 문제에 쿼드트리의 위키피디아 링크가 걸려 있으니 그걸 보자.

 

---

쿼드트리는 각 내부 노드에 정확히 4개의 자식이 있는 트리 데이터 구조입니다.

쿼드트리는 옥트리의 2차원 아날로그이며,

2차원 공간을 4개의 사분면 또는 영역으로 재귀적으로 세분화하여 분할하는 데 가장 자주 사용됩니다.

 

모든 형태의 쿼드트리는 몇 가지 공통된 특징을 공유합니다:

• 공간을 적응 가능한 셀로 분해합니다.
• 각 셀(또는 버킷)에는 최대 용량이 있습니다. 최대 용량에 도달하면 버킷이 분할됩니다.
• 트리 디렉토리는 쿼드트리의 공간 분해를 따릅니다.

---

일단 중요한 건, 일단 이거도 트리라는 거고 재귀로 접근할 수 있다는 것이다.

순서를 생각해 보자.

1. 먼저 좌상단에서 시작
2. 영역의 사이즈만큼 돌며 같은지 확인한다
3. 영역의 값들이 다 같다면 값을 늘린다
4. 다르다면 그 안에서 4개의 면으로 나누어 2번으로 돌아간다

문제에서 예시로 주는 과정도 이와 같다.

 

 

4개의 영역으로 더 이상 쪼갤 수 없을 때까지 쪼갠다.

이 과정을 코드로 옮기면 다음과 같다.

 

function solution(arr) {
    // 0 : 1
    const result = [0, 0];
    
    // 압축을 수행 할 재귀 함수
    function compress(x, y, size) {
        const area = arr[x][y]; // 시작지점 -> size만큼 더하거나 하여 위치를 표시
        let isSame = true;      // 각 영역의 값이 다 동일한지
        
        for(let i = x; i < x + size; i++) {
            for(let j = y; j < y + size; j++) {
                if(arr[i][j] != area) {     // 순회한 위치의 값이 영역의 값과 다를 때
                    isSame = false;
                    break;
                }
                // 기본 값이 true이므로 같으면 그냥 넘어간다
            }
            if(!isSame)
                break;
        }
        
        // 다 같으면 그 영역은 그걸로 끝
        // 더 쪼갤 필요가 없다.
        if(isSame)
            result[area]++;
        else {  // 다르면 각 사분면에 대해 재귀적으로 확인 수행
            const halfSize = size / 2;
            compress(x, y, halfSize);                           // 좌상
            compress(x, y + halfSize, halfSize);                // 우상
            compress(x + halfSize, y, halfSize);                // 좌하
            compress(x + halfSize, y + halfSize, halfSize);     // 우하
        }
    }
    
    compress(0, 0, arr.length);
    return result;
}

 

 

일단 재귀 이외의 아이디어가 떠오르지 않아 이렇게 나왔다.

함수 안에 재귀 함수를 두어 사용하는 것도 처음 해봤다.

어색 하지만 편한 것 같기도 하다.

 

결과도 꽤 괜찮은 것 같다.

최고가 10ms대니 꽤 효율적으로 동작한다고 볼 수 있을 것 같다.