Java 프로그래머스 쿼드압축 후 개수 세기 자바

문제출처 : https://school.programmers.co.kr/learn/courses/30/lessons/68936

프로그래머스

---

[문제 설명]

0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다.

당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

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

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

[제한사항]

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

[입출력 예]

[문제 풀기 전 생각]

• 각각의 1, 0의 위치 값을 나타낼 2차원 배열이 필요하다.
• 분할해서 확인 후, 해당 구역에 있는 숫자를 하나로 합침
• 즉 2차원 배열이 같은 수로 이루어져 있는지 확인 후 합치고 4등분, 확인 후 합치고 4등분이 n번 반복 되므로 재귀를 이용하면 된다!!

[나의 풀이]

public class Solution {
    int[] answer;

    public void quadZip(int[][] arr, int x, int y, int length){
        // 현재 영역이 압축 가능하면 answer 배열에 값 추가하고 반환
        if(zipChk(arr, x, y, length, arr[x][y])){
            if(arr[x][y] == 1) answer[1]++;
            else answer[0]++;
            return ;
        }
        
        // 1번 영역
        quadZip(arr, x, y, length/2);
        // 2번 영역
        quadZip(arr, x+length/2, y, length/2);
        // 3번 영역
        quadZip(arr, x, y+length/2, length/2);
        // 4번 영역
        quadZip(arr, x+length/2, y+length/2, length/2);
    }

    public boolean zipChk(int[][] arr, int x, int y, int length, int arrVal) {
        for(int i = x; i < x + length; i++){
            for(int j = y; j < y + length; j++){
                // 영역의 첫번째 값과 나머지를 비교하다 하나다로 다르면 반환
                if(arr[i][j] != arrVal) return false;
            }
        }
        return true;
    }
    
    public int[] solution(int[][] arr) {
        answer = new int[2];
        quadZip(arr, 0, 0, arr.length);
        return answer;
    }
}

• quadZip(주어진 2차원 배열, x축, y축, 주어진 2차원 배열 길이)
  • 주어진 2차원 배열 arr을 주어진 시작점 (x, y)와 길이 length를 기준으로 4 분할하여 압축한다.
  • 압축이 가능한 경우에는 압축된 결과를 저장하고, 더 이상 분할할 필요가 없을 때까지 재귀적으로 호출한다.
• zipChk(주어진 2차원 배열, x, y, 길이, (x, y) 좌표값)
  • 주어진 2차원 배열 arr에서 주어진 시작점 (x, y)와 길이 length를 기준으로 모든 요소가 동일한 값을 가지는지 확인하면서, 시작점부터 length만큼의 범위를 반복하면서 모든 요소의 값이 주어진 arrVal과 일치하는지 확인하여 true / false를 return 한다.

[정리]

개인 피셜 난이도 : ★★★★☆

재귀적 개념으로 적용하고 생각하는 것은 늘 어렵다.

개념적으로 경우의 수를 고려하여 매개변수와 호출 시점을 잡는 게 쉽지 않다.

또한 실무에서 재귀를 쓸 일이 많지 않다 보니 그만큼 무뎌지는 것도 사실이다.

때문에 참고해서 풀었음에도, 이해하기가 쉽지 않았다.

 

한동안 코딩 테스트 문제를 잘 안 풀었는데,

시간 날 때마다,

오래 걸리더라도,

내 힘으로 꼭 푸는 습관을 들여야겠다.

[참고]

다른 사람 풀이 : https://rovictory.tistory.com/143

(Java) 프로그래머스 - 쿼드 압축 후 개수 세기

 

언제나 새로운 정보 공유와 잘못된 정보 지적/태클은 환영입니다!

도움이 되셨다면 공감♥️, 댓글 부탁드려요:)

끝.