[68936] 쿼드압축 후 개수 세기

✔ 쿼드압축 후 개수 세기

[프로그래머스 68936]

문제 분석하기

n/2씩 크기를 줄여가며 압축 여부를 살펴보고 만약 압축될 수 있다면 0과 1의 개수를 갱신해줌

이때 이미 압축된 값을 다시 압축할 수 없으므로 방문 배열에 유무 갱신

 

예)

n이 8일 때, answer = [0, 0]

n이 4일 때, answer = [0 + 1, 0 + 1] = [1, 1]

n이 2일 때, answer = [1 + 2, 1 + 1] = [3, 2]

n이 1일 때, answer = [3 + 7, 2 + 13] = [10, 15]

손으로 풀어보기

1. n/2씩 크기를 줄여가며 압축 여부 확인
   • 압축이 가능하다면 0 또는 1의 개수에 (n * n) 추가
   • 압축한 위치에 대해 방문 유무 갱신
2. 압축한 값을 반환

슈도코드 작성하기

arr(0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열)
answer(배열에 최종적으로 남는 0의 개수와 1의 개수)
visited(방문 유무 배열)
n(arr의 길이)
size(압축하고자 하는 사각형의 크기)
while(size가 0보다 큰 동안) {
    사각형 함수(arr, n, size)
    size를 size/2로 갱신
}
answer 반환

사각형 함수 {
for(i -> 0부터 n까지 size만큼 증가) {
        for(j -> 0부터 n까지 size만큼 증가) {
            if(visited[i][j]를 방문하지 않았으면서 모두 0인지 또는 1인지 확인 함수가 true라면) {
                하나로 압축 가능하므로 answer[arr[i][j]]의 값을 1 증가
            }
        }
    }
}

모두 0인지 또는 1인지 확인 함수 {
    arr의 startX, startY좌표부터 startX + size, startY + size까지 모두 0이거나 1인지 확인
    모두 0이거나 1일 경우 그 좌표들을 모두 방문 처리
}

코드 구현하기

/**
 * 68936) 쿼드압축_후_개수_세기
 */
public class L060_68936 {
    // answer(배열에 최종적으로 남는 0의 개수와 1의 개수)
    static int[] answer;
    // visited(방문 유무 배열)
    static boolean[][] visited;

    // arr(0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열)
    public int[] solution(int[][] arr) {
        answer = new int[2];
        // n(arr의 길이)
        int n = arr.length;
        visited = new boolean[n][n];
        // size(압축하고자 하는 사각형의 크기)
        int size = n;
        while (size > 0) {
            // 사각형 함수(arr, n, size)
            square(arr, n, size);
            // size를 size/2로 갱신
            size /= 2;
        }
        // answer 반환
        return answer;
    }

    // 사각형 함수
    private static void square(int[][] arr, int n, int size) {
        for (int i = 0; i < n; i += size) {
            for (int j = 0; j < n; j += size) {
                // visited[i][j]를 방문하지 않았으면서 모두 0인지 또는 1인지 확인 함수가 true라면
                if (!visited[i][j] && isAllZerosOrOnes(arr, i, j, size)) {
                    // 사각형을 하나로 압축 가능하므로 answer[arr[i][j]]의 값을 1 증가
                    answer[arr[i][j]] += 1;
                }
            }
        }
    }

    // 모두 0인지 또는 1인지 확인 함수
    private static boolean isAllZerosOrOnes(int[][] arr, int startX, int startY, int size) {
        // arr의 startX, startY좌표부터 startX + size, startY + size까지 모두 0이거나 1인지 확인
        int value = arr[startX][startY];
        for (int i = startX; i < startX + size; i++) {
            for (int j = startY; j < startY + size; j++) {
                if (arr[i][j] != value) {
                    return false;
                }
            }
        }
        // 모두 0이거나 1일 경우 그 좌표들을 모두 방문 처리
        for (int i = startX; i < startX + size; i++) {
            for (int j = startY; j < startY + size; j++) {
                visited[i][j] = true;
            }
        }
        return true;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L060_68936 solution = new L060_68936();

        int[][] arr = {
                { 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 } };

        int[] result = solution.solution(arr);

        System.out.println(Arrays.toString(result));
    }
}