[프로그래머스] 쿼드압축 후 개수 세기 - JAVA

[프로그래머스] 쿼드압축 후 개수 세기 - JAVA

 

 

문제 설명

 

풀이과정

1. 구역을 정해서 그 구역이 0으로 채워있으면 0으로 압축, 1으로 채워져있으면 1로 압축하는 과정

     1-1. 만약, 모두 똑같은 숫자로 되어 있다면 zeroCnt  or oneCnt를 증가시킨다.

     1-2. 압축되지 않는다면 2번으로!

2. size/2 만큼 잘라서 재귀호출을 하여 1번의 과정을 반복한다.

     2-1. size/2를 자르고 포인트는 dx, dy를 아래와 같이 설정하는 것이다. 
           static double[] dx = {0, 0, 0.5, 0.5};
           static double[] dy = {0, 0.5, 0, 0.5};

 

 

 

내가 놓쳤던 부분

   - 전체가 똑같은 0이나 1로 채워져있는 경우를 반영해주지 않았다!

 

 

소스 코드 

import java.util.Arrays;

public class CountingAfterQuadCompression {
    public static void main(String[] args) {
        int[][] arr = {{1,1,0,0},{1,0,0,0},{1,0,0,1},{1,1,1,1}};

        System.out.println(Arrays.toString(solution(arr)));
    }

    static int zeroCnt = 0, oneCnt = 0;
    static double[] dx = {0, 0, 0.5, 0.5};
    static double[] dy = {0, 0.5, 0, 0.5};
    static int[][] copyArr;

    public static int[] solution(int[][] arr) {
        int[] answer = new int[2];
        copyArr = arr;

        if(!isCompression(arr.length, 0,0))
            compression(0,0, arr.length);
        answer[0] = zeroCnt;
        answer[1] = oneCnt;

        return answer;
    }

    public static void compression(int x, int y, int size) {

        for(int i=0; i<4; i++) {
            int nx = x + (int) (size * dx[i]);
            int ny = y + (int) (size * dy[i]);

            if( !isCompression(size/2, nx, ny) )
                compression(nx, ny, size/2);

        }
    }

    public static boolean isCompression(int size, int x, int y) {
        int num = copyArr[x][y];

        for(int i=x; i<x+size; i++) {
            for(int j= y; j<y+size; j++) {
                if(num != copyArr[i][j])
                    return false;
            }
        }

        if(num == 0) zeroCnt++;
        else oneCnt++;

        return true;
    }
}

 

 

 

programmers.co.kr/learn/courses/30/lessons/68936

코딩테스트 연습 - 쿼드압축 후 개수 세기