Programmers | Level 2 | 쿼드압축 후 개수 세기
Programmers | Level 2 | 쿼드압축 후 개수 세기
Problems
- 📘 Src: Programmers
- 🗂️ Cat: Divide and Conquer
Description
0과 1로 이루어진 2^n x 2^n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.
- 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
- 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
- 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.
arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.
Constraints
arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 가집니다.arr의 각 행 길이는arr의 행의 개수와 같으며, 모든 값은 0 또는 1입니다.
Examples
| 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] |
Solutions
Code
class Solution {
public int[] solution(int[][] arr) {
int[] result = {0, 0}; // 0의 개수와 1의 개수를 담을 배열
compress(arr, result, 0, 0, arr.length);
return result;
}
// arr: 2차원 배열
// result: 0과 1의 개수를 저장할 배열
// x: 2차원 배열의 시작 행 인덱스
// y: 2차원 배열의 시작 열 인덱스
// size: 정사각형의 한 변의 길이
private void compress(int[][] arr, int[] result, int x, int y, int size) {
if (isUniform(arr, x, y, size)) {
int bit = arr[x][y];
result[bit]++; // 해당 영역이 모두 같은 값이면 카운트 증가
return; // 더 이상 분할하지 않고 종료
}
int newSize = size / 2; // 영역을 4등분하여 압축 시도
compress(arr, result, x, y, newSize); // 1사분면
compress(arr, result, x + newSize, y, newSize); // 2사분면
compress(arr, result, x, y + newSize, newSize); // 3사분면
compress(arr, result, x + newSize, y + newSize, newSize); // 4사분면
}
private boolean isUniform(int[][] arr, int x, int y, int size) {
int first = arr[x][y]; // 첫 번째 값을 기준으로 비교
for (int i = x; i < x + size; i++) {
for (int j = y; j < y + size; j++) {
if (arr[i][j] != first) {
return false; // 영역 내에 다른 값이 존재하면 false 반환
}
}
}
return true; // 영역 내 모든 값이 같으면 true 반환
}
}
Approach
이 문제는 주어진 2차원 배열을 쿼드 트리 방식으로 압축하여 최종적으로 남은 0과 1의 개수를 계산하는 문제입니다. 핵심은 쿼드 트리 알고리즘을 이해하고 이를 분할 정복(Divide and Conquer) 기법을 통해 재귀적으로 구현하는 것입니다. 이 방식은 배열을 반복적으로 4개의 작은 영역으로 나누면서, 각 영역이 동일한 값을 가지는지 확인하고, 압축할 수 있으면 압축을, 그렇지 않으면 더 작은 단위로 분할하는 과정을 포함합니다.
1. 문제 분석
입력받은 arr 배열은 2^n x 2^n 크기를 가지며, 이 배열을 압축하는 방식은 다음과 같습니다:
- 압축할 영역이 모두 동일한 값으로 이루어져 있으면, 이 영역을 하나의 값으로 압축합니다.
- 그렇지 않으면, 영역을 네 개의 동일한 크기의 정사각형으로 나누어 각 영역에 대해 압축을 시도합니다.
- 최종적으로 0과 1이 각각 몇 개 남는지를 계산하여 결과로 반환합니다.
2. 접근 방식
이 문제는 분할 정복(Divide and Conquer) 기법을 사용하여 해결할 수 있습니다.
- 전체 배열을 네 개의 균일한 부분으로 나누고, 각 부분이 동일한 값을 가지는지 확인하여 압축을 진행합니다.
- 모든 영역이 같은 값이 아니면, 다시 네 개로 나누어 같은 과정을 반복합니다.
- 이 과정을 재귀적으로 구현하여 문제를 해결합니다.
3. 쿼드 트리 압축 구현
배열의 압축을 위한 재귀 함수를 구현합니다. 이 함수는 주어진 영역이 모두 동일한 값인지 확인한 후, 동일한 값으로 이루어져 있다면 해당 값을 카운트하고, 그렇지 않다면 영역을 네 개로 나누어 각각에 대해 다시 압축을 시도합니다:
private void compress(
int[][] arr, // 2차원 배열 전체
int[] result, // 0과 1의 개수를 저장할 배열
int x, // 현재 처리 중인 2차원 배열의 시작 행 인덱스
int y, // 현재 처리 중인 2차원 배열의 시작 열 인덱스
int size // 현재 탐색할 영역의 크기 (정사각형의 한 변의 길이)
) {
// 기저 조건: 주어진 영역이 모두 동일한 값인지 확인
if (isUniform(arr, x, y, size)) {
int bit = arr[x][y]; // 해당 영역의 값이 0인지 1인지 확인
result[bit]++; // 해당 값의 개수를 증가시킴 (0이면 result[0], 1이면 result[1])
return; // 더 이상 분할하지 않고 종료
}
// 주어진 영역이 동일하지 않다면, 네 개로 분할하여 재귀적으로 처리
int newSize = size / 2; // 영역을 4등분하여 새로운 크기를 설정
compress(arr, result, x, y, newSize); // 1사분면
compress(arr, result, x + newSize, y, newSize); // 2사분면
compress(arr, result, x, y + newSize, newSize); // 3사분면
compress(arr, result, x + newSize, y + newSize, newSize); // 4사분면
}
compress():- 이 재귀 함수는 배열의 특정 영역을 처리하며, 만약 해당 영역이 기저 함수에서 동일한 값으로 판정되면 그 값을 카운트합니다. 그렇지 않으면 해당 영역을 네 개의 동일한 크기의 하위 영역으로 분할한 후, 각 부분에 대해
compress()를 재귀적으로 호출합니다. - 이 분할 과정은 배열이 2의 제곱근 크기를 가지기 때문에 가능하며, 이를 통해 각 영역을 계속해서 반으로 나누어 네 개의 하위 영역으로 나누는 작업이 이루어집니다. 이 과정은 더 이상 분할할 수 없을 때까지 반복됩니다.
- 이 재귀 함수는 배열의 특정 영역을 처리하며, 만약 해당 영역이 기저 함수에서 동일한 값으로 판정되면 그 값을 카운트합니다. 그렇지 않으면 해당 영역을 네 개의 동일한 크기의 하위 영역으로 분할한 후, 각 부분에 대해
isUniform():- 이 함수는 지정된 영역이 모두 동일한 값으로 구성되어 있는지 확인하며, 재귀 호출에서 기저 조건(Base Case)에 해당합니다.
- 만약 모든 값이 같다면, 더 이상 영역을 분할하지 않고 해당 값
0또는1을 카운트합니다. 기저 조건이 충족되면 재귀 호출을 멈추고 결과를 반환합니다.
다음은 compress(arr, result, 0, 0, 8)이 처음 호출되었을 때, 재귀적으로 호출되는 과정에서 변화되는 x, y, size 값을 나타낸 예시입니다:
| 호출 순서 | x | y | size | 설명 |
|---|---|---|---|---|
| 1 | 0 | 0 | 8 | 전체 배열을 처리 |
| 2 | 0 | 0 | 4 | 1사분면 처리 |
| 3 | 4 | 0 | 4 | 2사분면 처리 |
| 4 | 0 | 4 | 4 | 3사분면 처리 |
| 5 | 4 | 4 | 4 | 4사분면 처리 |
| 6 | 0 | 0 | 2 | 1사분면을 더 작은 영역으로 나눔 |
| ... | ... | ... | ... | ... |
이 과정을 통해 배열 전체를 작은 영역으로 나누어 재귀적으로 처리하며, 각 영역의 값을 압축하고, 결과적으로 남은 0과 1의 개수를 계산합니다.
4. 단일 영역 확인
압축할 영역이 모두 동일한 값을 가지는지 확인하는 함수를 구현합니다. 이 함수는 주어진 영역의 모든 값을 검사하여, 모든 값이 동일하면 true를 반환하고, 하나라도 다른 값이 존재하면 false를 반환합니다. 이 함수는 재귀 함수에서 기저 조건(Base Case)을 확인하는 역할을 하며, 재귀 호출을 종료할지 여부를 결정하는 중요한 부분입니다.
// 현재 영역의 모든 요소들이 동일한 값인지 확인
private boolean isUniform(
int[][] arr, // 2차원 배열 전체
int x, // 현재 처리 중인 2차원 배열의 시작 행 인덱스
int y, // 현재 처리 중인 2차원 배열의 시작 열 인덱스
int size // 현재 탐색할 영역의 크기 (정사각형의 한 변의 길이)
) {
int first = arr[x][y]; // 첫 번째 값을 기준으로 비교
for (int i = x; i < x + size; i++) { // 행 루프: 시작 위치 x부터 size만큼 반복
for (int j = y; j < y + size; j++) { // 열 루프: 시작 위치 y부터 size만큼 반복
if (arr[i][j] != first) {
return false; // 영역 내에 다른 값이 존재하면 false 반환
}
}
}
return true; // 영역 내 모든 값이 동일하면 true 반환
}
- 첫 번째 값 기준 비교:
first변수는 비교의 기준이 되는 값으로, 검사할 영역의 첫 번째 값을 저장합니다. 이 값과 영역 내 다른 모든 값들을 비교하여 동일한지 확인합니다. - 이중 반복문: 두 개의 중첩된
for루프를 사용하여, 지정된 영역 내의 모든 값을 순차적으로 검사합니다. 만약first값과 다른 값이 발견되면false를 반환하여 해당 영역이 동일한 값으로 이루어지지 않았음을 알립니다. - 결과 반환: 모든 값이 동일하다면,
true를 반환하여 이 영역을 더 이상 분할할 필요가 없음을 알립니다. 그렇지 않다면,false를 반환하여 더 작은 영역으로 분할이 필요함을 나타냅니다.
이 함수는 재귀 함수의 기저 조건을 확인하는 역할을 하므로, 배열 압축의 핵심적인 부분을 담당합니다.
5. 최종 결과 반환
재귀적으로 쿼드 트리 압축을 완료한 후, 최종적으로 남은 0과 1의 개수를 반환합니다.
// 초기 결과 배열과 함께 압축 시작
int[] result = {0, 0};
compress(arr, result, 0, 0, arr.length);
return result;
Complexity
- ⏳ TC: O(n^2)
- 💾 SC: O(log n)
이 알고리즘의 시간 복잡도는 배열 전체를 검사하기 때문에 O(n^2)입니다. 재귀적으로 영역을 나누기 때문에 공간 복잡도는 O(log n)입니다. 이 문제는 쿼드 트리 알고리즘을 사용하여 배열을 효율적으로 압축하고, 압축된 결과에서 0과 1의 개수를 정확히 세는 방법을 학습할 수 있습니다.
- Algorithm
- Divide and Conquer