재귀를 잘 정의해서 좋으면 코드로 옮기는 작업은 간단하고 문제도 쉽게 해결해줍니다. 하지만 재귀를 충분히 익히지 않은 채로 코드부터 작성하기 시작한다면 코드 작성과 재귀 호출이 헷갈려 중간에 꼬일 가능성이 높습니다. 따라서 문제를 잘 파악하고 재귀를 올바르게 정의하는 연습을 해야 합니다.
전체 코드
5장/쿼드압축후_개수_세기.java
public class Solution {
private static class Count {
public final int zero;
public final int one;
public Count(int zero, int one) {
this.zero = zero;
this.one = one;
}
public Count add(Count other) {
return new Count(zero + other.zero, one + other.one);
}
}
private Count count(int offsetX, int offsetY, int size, int[][] arr) {
int h = size / 2;
for (int x = offsetX; x < offsetX + size; x++) {
for (int y = offsetY; y < offsetY + size; y++) {
if (arr[y][x] != arr[offsetY][offsetX]) {
return count(offsetX, offsetY, h, arr)
.add(count(offsetX + h, offsetY, h, arr))
.add(count(offsetX, offsetY + h, h, arr))
.add(count(offsetX + h, offsetY + h, h, arr));
}
}
}
if (arr[offsetY][offsetX] == 1) {
return new Count(0, 1);
}
return new Count(1, 0);
}
public int[] solution(int[][] arr) {
Count count = count(0, 0, arr.length, arr);
return new int[] {count.zero, count.one};
}
}