728x90
📝 문제 설명
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 입니다.
🖨 입출력 예
answer | 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] |
📂 분류
재귀
, 분할정복
💡 풀이
분할 정복의 대표적인 문제이다.
❗️접근 방법
n
이 1이라면 해당 영역의 값의 개수를 증가시킨다.isPossibleCompression
메서드를 이용하여 압축이 가능한지 판단한다.- 2의 제곱수 배열이 주어지기 때문에 분할할 때
n
을 2로 나눠준다.
💻 코드
public class Solution {
int[] count = new int[2];
int[][] quadtree;
public int[] solution(int[][] arr) {
quadtree = arr;
int n = arr.length;
Compress(n, 0, 0);
return count;
}
private void Compress(int n, int y, int x) {
int cur = quadtree[y][x];
if (n == 1 || isPossibleCompression(n, y, x)) {
count[cur] += 1;
} else {
int scope = n / 2;
Compress(scope, y, x); // 좌상
Compress(scope, y, x + scope); // 우상
Compress(scope, y + scope, x); // 좌하
Compress(scope, y + scope, x + scope); // 우하
}
}
private boolean isPossibleCompression(int n, int y, int x) {
int cur = quadtree[y][x];
for (int i = y; i < y + n; i++) {
for (int j = x; j < x + n; j++) {
if (cur != quadtree[i][j]) {
return false;
}
}
}
return true;
}
}
728x90
'Algorithm > 프로그래머스' 카테고리의 다른 글
[Java] 프로그래머스 Lv2 - 방문 길이 (0) | 2022.04.15 |
---|---|
[Java] 프로그래머스 Lv2 - 스킬트리 (0) | 2022.04.15 |
[Java] 프로그래머스 Lv2 - n^2 배열 자르기 (0) | 2022.04.12 |
[Java] 프로그래머스 - 로또의 최고 순위와 최저 순위(Level 1) (0) | 2022.04.10 |
[Java] 프로그래머스 - 점프와 순간 이동 (Level 2) (0) | 2022.04.09 |