🎯문제
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 입니다.
입출력 예
| arr | result |
|---|---|
| [[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 해야 합니다.
✏️풀이
코드
class Solution {
int[] answer;
// 압축 가능 여부를 판단하는 메서드
public boolean check(int[][] arr, int x, int y, int size, int temp) {
for(int i = x; i < x + size; i++) {
for(int j = y; j < y + size; j++) {
if(arr[i][j] != temp) {
return false;
}
}
}
return true;
}
// 쿼드 압축을 진행하는 메서드
public void quad(int[][] arr, int x, int y, int size) {
// 압축이 가능하다면
if(check(arr, x, y, size, arr[x][y])) {
// 0 혹은 1의 값을 증가
int temp = arr[x][y] == 0 ? answer[0]++ : answer[1]++;
return;
}
// 구간을 나눠서 확인
// 왼쪽 위
quad(arr, x, y, size/2);
// 왼쪽 아래
quad(arr, x, y + size/2, size/2);
// 오른쪽 위
quad(arr, x + size/2, y, size/2);
// 오른쪽 아래
quad(arr, x + size/2, y + size/2, size/2);
}
public int[] solution(int[][] arr) {
answer = new int[2];
quad(arr, 0, 0, arr.length);
return answer;
}
}설명
메서드를 직접 만드는 방식을 사용하였다.
쿼드 압축을 진행하기 위해선 해당 구간이 모두 같은 숫자여야한다. 또한 압축을 진행하지 못하면 해당 구간을 4개의 같은 정사각형으로 나눠준 뒤 각각의 구간에서 다시 압축이 가능한지 확인을 진행한다.
quad 메서드를 먼저 살펴보면 주어진 2차원 배열과 시작하는 x, y 좌표, 구간의 크기가 매개변수로 넘어온다.
check 메서드를 통해 값을 확인하는데, 해당 메서드는 quad 메서드의 설명이 끝난 뒤에 얘기를 하도록 하겠다.
check 메서드를 통해 압축이 가능한지 확인을 하고 만약 가능하다면 0으로 압축을 하는지 1로 압축을 하는지 확인하여 해당 부분의 배열의 값을 증가시켜준다. answer[0]은 0으로 압축하는 개수이고, answer[1]은 1로 압축하는 개수이다.
만일 압축이 불가능하다면, 4개의 구간으로 나눠서 값을 확인한다. 이때 재귀호출 방식을 사용하는데 size/2를 사용해 값을 절반으로 나눠주고 x, y의 시작 위치를 바꿔서 4개의 구간으로 나눠준다. (x, y)이 (0, 0) 시작이므로 맨 위는 (0, 0) 그대로 진행을 하게 되고 크기는 가로 세로 절반씩 줄어들기에 1/4이 된다. (x, y+size/2)는 x = 0이고 만일 size = 8 이었다면 y = 4가 된다. (0, 4) 이므로 오른쪽 위의 구간을 나타내게 된다. 위와 같은 방식으로 x에도 size/2를 더해주어 왼쪽 아래, x, y 모두 size/2를 더해주어 오른쪽 아래의 압축을 진행한다.
check 메서드는 압축이 가능한지 확인하는 메서드로 압축이 가능하다면 true 아니라면 false를 반환해준다. size만큼 반복을 진행하며 시작 위치는 x, y 좌표이다. 해당 반복을 진행하면서 모든 값이 temp와 같을 때 해당 부분은 압축이 가능하다. 만일 반복 도중 하나라도 값이 다르다면 해당 부분은 압축이 불가능하다.
위의 두 메서드를 사용하여 문제를 해결할 수 있다!
💡느낀 점
이전에 한번 쿼드 압축 문제를 풀어본 적이 있었다. 그 기억 덕분인지 조금 더 쉽게 해결할 수 있었다. 특히나 어떤 방식을 사용하는 것은 좀 어려웠지만 직접 메서드를 만들어서 구현하는 문제들은 자유도가 높아서 조금 더 재밌는 것 같다. 그렇지만 이런 문제만 풀 순 없으니 다양한 유형의 문제들을 풀도록 노력해야겠다..
링크
