[프로그래머스] Lv. 2 쿼드압축 후 개수 세기(Java)
by rowing0328https://school.programmers.co.kr/learn/courses/30/lessons/68936
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
정답 코드
class Solution {
private static class Count {
public final int zero;
public final int one;
public Count(final int zero, final int one) {
this.zero = zero;
this.one = one;
}
public Count add(final Count other) {
return new Count(zero + other.zero, one + other.one);
}
}
private Count count(final int offsetX, final int offsetY, final int size, final 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(final int[][] arr) {
final Count count = count(0, 0, arr.length, arr);
return new int[] {count.zero, count.one};
}
}
설명
2차원 배열을 탐색하며 특정 조건을 만족하는 영역을 찾는 문제는
분할 정복(Divide and Conquer) 방식으로 해결할 수 있다.
이번 문제에서는 배열을 4등분하여 재귀적으로 탐색하면서
0과 1의 개수를 구하는 방법을 설명한다.
- 배열의 시작 위치(offsetX, offsetY)와 크기(size)를 기준으로 해당 영역을 탐색한다.
- 반복문을 통해 해당 영역의 모든 값을 확인하고, 기준 값과 다른 값이 있는지 검사한다.
- 모든 값이 같으면 현재 영역의 값(0 또는 1)을 반환한다.
- 값이 섞여 있다면 배열을 4 등분하여 각 영역에 대해 재귀 호출을 수행한다.
- 각 영역의 결과를 합산하여 최종 결과로 반환한다.
실행 결과
참고 자료 :
취업과 이직을 위한 프로그래머스 코딩 테스트 문제 풀이 전략 : 자바 편 | 김현이
프로그래머스 코딩 테스트 문제 풀이 전략: 자바 편 | 김현이 - 교보문고
프로그래머스 코딩 테스트 문제 풀이 전략: 자바 편 | 핵심 개념, 프로그래머스에서 선별한 79개 문제 풀이, PCCP 대비까지! 합격에 한 걸음 더 가까워지는 실전형 코딩 테스트 문제 풀이 가이드개
product.kyobobook.co.kr
'🏅Algorithm > Programmers' 카테고리의 다른 글
[프로그래머스] Lv. 2 모음사전(Java) (0) | 2025.02.16 |
---|---|
[프로그래머스] Lv. 2 이진 변환 반복하기(Java) (0) | 2025.02.03 |
[프로그래머스] Lv. 1 신규 아이디 추천(Java) (0) | 2025.02.03 |
[프로그래머스] Lv. 1 문자열 다루기 기본(Java) (0) | 2025.02.03 |
[프로그래머스] Lv. 1 숫자 문자열과 영단어(Java) (0) | 2025.02.03 |
블로그의 정보
코드의 여백
rowing0328