코드의 여백

[프로그래머스] Lv. 2 쿼드압축 후 개수 세기(Java)

by rowing0328
https://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의 개수를 구하는 방법을 설명한다.

 

  1. 배열의 시작 위치(offsetX, offsetY)와 크기(size)를 기준으로 해당 영역을 탐색한다.
  2. 반복문을 통해 해당 영역의 모든 값을 확인하고, 기준 값과 다른 값이 있는지 검사한다.
  3. 모든 값이 같으면 현재 영역의 값(0 또는 1)을 반환한다.
  4. 값이 섞여 있다면 배열을 4 등분하여 각 영역에 대해 재귀 호출을 수행한다.
  5. 각 영역의 결과를 합산하여 최종 결과로 반환한다.

 

실행 결과

 

참고 자료 :

취업과 이직을 위한 프로그래머스 코딩 테스트 문제 풀이 전략 : 자바 편 | 김현이

 

프로그래머스 코딩 테스트 문제 풀이 전략: 자바 편 | 김현이 - 교보문고

프로그래머스 코딩 테스트 문제 풀이 전략: 자바 편 | 핵심 개념, 프로그래머스에서 선별한 79개 문제 풀이, PCCP 대비까지! 합격에 한 걸음 더 가까워지는 실전형 코딩 테스트 문제 풀이 가이드개

product.kyobobook.co.kr

블로그의 정보

코드의 여백

rowing0328

활동하기