[알고리즘] 프로그래머스 쿼드압축 후 개수 세기 (월드 코드 챌린지 시즌 1) -dfs, 백트랙킹- 자바 코틀린

programmers.co.kr/learn/courses/30/lessons/68936?language=java

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

 

 

프로그래머스 월드 코드 챌린지 시즌1 LV2 문제인 쿼드압축 후 개수 세기 문제를 풀어봤습니다. ㅎㅎ

 

0또는 1을 담은 n^2 의 정사각형을 4분의 1 조각으로 계속해서 나누면서 조각이 같은 값을 갖고있으면 압축하고 마지막에 0 또는 1의 개수 결과를 리턴하는 문제입니다.

 

풀이는 다음과 같습니다.

 

[Java]

class Solution {
    private static int[][] map;
    private static int zero = 0;
    private static int one = 0;

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(new int[][]{{1, 1, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 1}, {1, 1, 1, 1}});
    }

    private static void dfs(int n, int x, int y) {
        if (n == 1) { // 한개인 경우 해당 값 +
            if (map[x][y] == 1) {
                one++;
            } else {
                zero++;
            }
            return;
        }
        if (isSame(n, x, y)) { //같은값인지 압축 가능한지
            return;
        }
        //4개 분리 탐색
        dfs(n / 2, x, y);
        dfs(n / 2, x + n / 2, y);
        dfs(n / 2, x, y + n / 2);
        dfs(n / 2, x + n / 2, y + n / 2);
    }

    public static boolean isSame(int n, int x, int y) {
        int first = map[x][y];
        for (int i = x; i < x + n; i++) {
            for (int j = y; j < y + n; j++) {
                if (first != map[i][j]) {
                    return false;
                }
            }
        }
        //압축 가능하면 해당 값 +1
        if (first == 0) {
            zero += 1;
        } else {
            one += 1;
        }
        return true;
    }

    public int[] solution(int[][] arr) {
        int[] answer = new int[2];
        map = arr;
        dfs(arr.length, 0, 0);
        answer[0] = zero;
        answer[1] = one;
        return answer;
    }

}

 

 

[Kotlin]

class Solution {
    private lateinit var map: Array<IntArray>
    private var zero = 0
    private var one = 0
    fun solution(arr: Array<IntArray>): IntArray {
        val answer = IntArray(2)
        map = arr
        dfs(arr.size, 0, 0)
        answer[0] = zero
        answer[1] = one
        return answer
    }

    private fun dfs(n: Int, x: Int, y: Int) {
        if (n == 1) {
            if (map[x][y] == 1) {
                one++
            } else {
                zero++
            }
            return
        }
        if (isSame(n, x, y)) {
            return
        }
        dfs(n / 2, x, y)
        dfs(n / 2, x + n / 2, y)
        dfs(n / 2, x, y + n / 2)
        dfs(n / 2, x + n / 2, y + n / 2)
    }

    private fun isSame(n: Int, x: Int, y: Int): Boolean {
        val first = map[x][y]
        for (i in x until x + n) {
            for (j in y until y + n) {
                if (first != map[i][j]) {
                    return false
                }
            }
        }
        if (first == 0) {
            zero += 1
        } else {
            one += 1
        }
        return true
    }

}

 

 

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다 !!