[프로그래머스] Lv.2 쿼드 압축 후 개수 세기 문제 해결과정(Java)

 문제 링크

---

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

프로그래머스

 

 

 해결 과정

---

 이 문제를 보고 크기가 큰 배열부터 파악해서, 압축할 수 있으면 압축하고, 못하면 넘어가는 방식으로 해결하면 될 것이라 생각했습니다. 그리고 압축하면 압축했다는 플래그를 설정하여 최대한 같은 배열을 탐색하지 못하도록 설정했습니다. 

 

 그리고 문제에서 중요하다고 생각하는 배열을 탐색하는 크기를 설정하는 방법이라고 생각하는데, 이 부분은 반복문의 증감을 잘 설정해서 해결했습니다!

 

채점 결과

 

 

 전체 코드

---

/*
    크기가 큰 배열부터 압축.
    압축 후 압축했다는 플래그 설정
    7 9 -> 4 9 
*/
class Solution {
    public int[] solution(int[][] arr) {
        int[] answer = {0,0};
        for(int[] a : arr) {
            for(int n : a) {
                answer[n]++;
            }
        }
        return compress(arr, answer);
    }
    
    private int[] compress(int[][] arr, int[] answer) {
        int length = arr.length;
        boolean[][] compressed = new boolean[length][length];
        
        while(length > 1) {
            for(int i  = 0; i < arr.length; i += length) {
                for(int j = 0; j < arr.length; j += length) {
                    //압축 되지 않았다면 해당 영역을 탐색.
                    if(!compressed[i][j]) {
                        //1개수 구하기
                        int count = countOne(arr, i, j, length);
                        setCount(length, count, answer, compressed, i, j);
                    }
                }
            }
            //탐색 배열 크기를 1/4로 줄임
            length /= 2;
        }
        return answer;
    }
    
    private int countOne(int[][] arr, int i, int j, int length) {
        int count = 0;
        for(int x = i; x < i+length; x++) {
            for(int y = j; y < j+length; y++) {
                if(arr[x][y] == 1) {
                    count++;
                }
            }
        }
        return count;
    }
    
    private void setCount(int length, int count, int[] arr, boolean[][] flag, int i, int j) {
        //탐색한 영역이 모두다 0또는 1로 되어있다면 압축 후 플래그 설정
        int total = length*length;
        if(count == total) {
            arr[1] += (1-total);
            setFlag(flag, i, j, length);
        } else if(count == 0) {
            arr[0] += (1-total);
            setFlag(flag, i, j, length);
        }
    }
    
    private void setFlag(boolean[][] flag, int i, int j, int length) {
        for(int x = i; x < i+length; x++) {
            for(int y = j; y < j+length; y++) {
                flag[x][y] = true;
            }
        }
    }
}

 

 

 정리

---

• 문제를 천천히 읽어보고 생각해 보자