(알고리즘 스터디) 9주차 금_(Programmers) 쿼드압축 후 개수 세기

🌟 프로그래머스 / 월간 코드 챌린지 시즌 1 / Level 2 / 쿼드압축 후 개수 세기

📃 문제

프로그래머스

🚫 제한 사항

• 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️⃣ 기본 아이디어

➡️ 최대 크기 (= 배열의 크기) 부터 시작해서 1/2 씩 줄여나간다. 줄여나가는 과정에서는 재귀가 쓰인다.

2️⃣ 1 과 0 의 개수 확인

➡️ 전체를 탐색하며 one (= 1의 개수) 을 확인한다. 전체 원소의 개수에서 one 을 빼면 zero (= 0의 개수) 이다.

3️⃣ 설명 (입출력 예 2번)

① limit = 8

➡️ 길이(=l imit) 가 8인 경우는 가능한 경우들 중 가장 최대 크기이다. (0,0) 부터 확인하며 계속해서 같은 값이 나오는지 확인한다. 현재 상태에서는 (1,0) 에서 문제가 생기므로 4개의 균일한 정사각형으로 쪼개져야한다.

// 첫번째 원소
int tmp = Arr[x][y]; 

// 탐색
for (int i=x; i<x+limit; i++) {
    for (int j=y; j<y+limit; j++) {                
        if (tmp != Arr[i][j]) { // 경우 ① : 압축에 실패할 경우 ➡️ 분할
            // 다음 단계에서 확인
        }
    }
}

② limit = 4

➡️ 4개의 균일한 정사각형으로 분할한 모습이다. 각 시작 지점이 그 다음 최대 크기인 길이가 4 (= 8/2) 를 분기로 끊어 지게 되어 (0,0) / (0,4) / (4,0) / (4,4) 총 4개가 된다.

// 기존 길이에서 절반으로 줄임
limit = limit / 2;
// 4개의 분기로 분할
quad(x, y, limit);
quad(x, y + limit, limit);
quad(x + limit, y, limit);
quad(x + limit, y+limit, limit);

③ limit = 2

➡️ 먼저 위 그림에서의 두번째, 세번째 분할 구역을 보면 모두 1 또는 0 으로 이루어졌기 때문에 압축이 가능하다. 해당 과정에서 개수는 Math.pow(limit,2) -1 개 만큼 줄어든다.

➡️ 다음 첫번째와 네번째 분할 구역을 보면 앞선 경우와 마찬가지로 다시한번 분할되어야한다. 따라서 다음 최대 크기인 길이 2 가 분기가 된다. 지금부터는 첫번째 분할 구역만 집중적으로 확인하도록 하자.

// 경우 ② : 압축에 성공한 경우 ➡️ 압축한 만큼 개수 제거
if (tmp == 1) {
    one = one - ((int)Math.pow(limit, 2)-1);
    return;
}
zero = zero - ((int)Math.pow(limit, 2)-1);
return;

④ limit = 1

➡️ 앞에서의 분할 구역 중 두번째, 네번째 구역은 압축 가능하여 개수가 줄어든다.

➡️ 하지만 첫번째, 세번째 구역은 다시 쪼개서야한다. 이때 길이는 1 이 되는데 이럴 경우 더 이상 쪼갤 수 없으며, 동시에 개수에 변화도 없어진다.

// 마지막 한 칸까지 온 경우 : 바로 return (개수 변화 없음)
if (limit == 1) { 
    return;
}

➡️ 위 내용들을 종합하면 아래와 같은 코드로 정리할 수 있다.

class Solution {
    // 1 과 0 의 개수
    public static int one = 0;
    public static int zero;
    public static int[][] Arr;
    
    public int[] solution(int[][] arr) {
        Arr = arr;
        
        // 크기
        int size = arr.length;
        
        // ① 전체를 탐색하며 1 과 0 의 개수 파악
        for (int i=0; i<size; i++) {
            for (int j=0; j<size; j++) {
                one += arr[i][j];
            }
        }
        zero = (int) Math.pow(size,2) - one;
        
        // ② 탐색
        quad(0, 0, size);
        
        // 배열 생성 후 반환
        return new int[] {zero,one};
    }
    public static void quad(int x, int y, int limit) {
        // 첫번째 원소 확인
        int tmp = Arr[x][y];
        
        if (limit == 1) { // 마지막 한 칸까지 온 경우 : 바로 return (개수 변화 없음)
            return;
        }
        
        // 탐색
        for (int i=x; i<x+limit; i++) {
            for (int j=y; j<y+limit; j++) {                
                if (tmp != Arr[i][j]) { // 경우 ① : 압축에 실패할 경우 ➡️ 분할
                    limit = limit / 2;
                    quad(x, y, limit);
                    quad(x, y + limit, limit);
                    quad(x + limit, y, limit);
                    quad(x + limit, y+limit, limit);
                    return;
                }
            }
        }
        
        // 경우 ② : 압축에 성공한 경우 ➡️ 압축한 만큼 개수 제거
        if (tmp == 1) {
            one = one - ((int)Math.pow(limit, 2)-1);
            return;
        }
        zero = zero - ((int)Math.pow(limit, 2)-1);
        return;
    }    
}

💻 풀이 코드

[level 2] Title: 쿼드압축 후 개수 세기, Time: 9.62 ms, Memory: 95.9 MB -Baekjo… · Young998904/Practice_Algorithm_Aut