[ 프로그래머스 > 월간 코드 챌린지 시즌1 ]LEVEL 2 : 쿼드압축 후 개수 세기, solved by java

문제 설명

0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

1. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다.
  • arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다.
  • arr의 각 행에 있는 모든 값은 0 또는 1 입니다.

---

입출력 예

arrresult

[[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

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.

• 

• 최종 압축 결과에 0이 4개, 1이 9개 있으므로, [4,9]를 return 해야 합니다.

입출력 예 #2

• 다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.

• 

• 최종 압축 결과에 0이 10개, 1이 15개 있으므로, [10,15]를 return 해야 합니다.

 

[ 풀이 코드 ] 

 

import java.util.*;
class Solution {
    public int[] solution(int[][] arr) {
        int[] answer = new int[2];
        int N = arr.length;
        for(int i =0; i< N; i++){
            for(int j = 0; j< N; j++){
                if(arr[i][j]==0)answer[0]++;
                else if(arr[i][j]==1)answer[1]++;
            }
        }
        boolean[][] v = new boolean[N][N];
        for(int n = N; n>1 ; n/=2){// 쪼개는 크기를 알려줌, 4->2->1
            for(int i = 0; i< N; i+=n){ //      0
                for(int j = 0; j< N; j+=n){ //  0
                    if(v[i][j])continue;
                    int flag = arr[i][j];
                    int a =i, b = j;
                    loop: 
                    for(a=i; a<i+n; a++){
                        for(b=j; b<j+n; b++){
                           if(flag!=arr[a][b])break loop;
                        }
                    }
                    if(a==i+n && b == j+n){
                        for(a=i; a<i+n; a++){
                            for(b= j ; b<j+n; b++){
                                v[a][b] = true;
                            }
                        }
                        answer[flag]-=n*n;
                        answer[flag]++;
                    }
                }
            }
        }
        return answer;
    }
}

멀쩡한 에디터 두고 연습하겠다고 프로그래머스에 바로 바로 푸는 사람이 바로 난데, 그래서 진짜 서터레스 받는다 후.. 

프로그래머스 너무 시렁.. 변수들 왜 요모양인지..  보기도 힘들엉

어쨋든 문제는 주어진 그림에 맞게 해석해서 풀면 된다. 

그림을 보면 큰 순서대로 다 같은값인지를 확인하고, 모두 같으면 그걸 하나로 압축 하는 방식이다. 

계산을 위해서 압축이 되면 그 값들을 제거하면 0의 개수와 1의 개수를 출력할 수 있다. 

그래서 처음 해준 작업은 

이렇게 해서 1의 개수와 0의 개수를 모두 세어 answer에 담아 주었다. 

그리고 이제 압축을 하면서 만약 크기가 4일때 압축을 하면 4*4 = 16 이던게 하나의 값으로 바뀌므로, 

이렇게 해준다고 생각하고, 

이제 큰 n부터 돌아가면서 값들이 모두 동일한지 확인해 준다. 큰 순서대로 압축해 주기때문에 한번 압축한걸 다시 압축하면 안된다. 그래서 압축 여부를 확인할 boolean배열을 하나 선언해 준다. 

그리고 이제 가장 크게 압축할 수 있는 N 부터, 1은 할 필요가 없으므로 1보다 큰 값까지 n을 1/2로 줄여가면서 반복문을 돌게 된다. 

 

반복문을 선언해주고, n의 크기에 따라서 i, j값을 다음값에는 i+=n이 되면서 반복문을 돌게 된다. 

그 중에서 v[i][j]를 통해 현재 값이 이미 압축되어 있으면 continue그냥 지나가게되고,

그렇지 않으면 모두 같은 값인지 검사해준다. 

 

먼저 flag로 최초의 값을 넣어주고, 

모두 같은값인지 확인해주기 위해 반복문 밖에 a, b를 선언해주고, 

반복문을 돌면서 하나라도 다른 값이 나타나면 반복문을 break해준다. 

 

만약 반복문을 끝까지 다른 값없이 모두 돌았다면, if문을 통해 압축을 수행해준다. 

방금 검사했던 그 값 그대로를 이용해서 , v[a][b]값을 압축처리 해준다. 

그리고, answer[flag]에 n*n을 빼고, 다시 1만 더해준다. 

그러면 압축된 flag의 숫자가 계산된다. 

 

이 과정을 n을 1/2로 줄여가면서 1보다 클때까지 반복해주면 answer가 계산되고, 이를 retrun 하면 된다. 

효율성은 이정도 나오게 된다