프로그래머스 쿼드압축 후 개수 세기(lvl2) 풀어보기

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/68936

프로그래머스

---

문제 핵심

0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

1. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.

arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

---

알고리즘

1.전체가동일수인지검사

2.아니라면 절반씩 영역분리

3.다시 전체가 동일수인지검사

4.반복

---

코드

 public static int[] solution(int[][] arr) {

        int[] answer = new int[2];

        int[][] arrClone = arr.clone();

        Map<Integer, Integer> count = new HashMap<>();

        dfs(arrClone, count, 0);

        System.out.println(count);

        answer[0] = count.getOrDefault(0, 0);

        answer[1] = count.getOrDefault(1, 0);

        System.out.println(Arrays.toString(answer));

        return answer;

    }

    public static void dfs(int[][] arr, Map<Integer, Integer> count, int index) {

        if (index == 0) {

            int first = arr[0][0];

            boolean allSame = Arrays.stream(arr)

                    .flatMapToInt(Arrays::stream)

                    .allMatch(n -> n == first);

            if (allSame) {

                System.out.println("첫배열이 모두일치");

                count.put(first, count.getOrDefault(first, 0) + 1);

                return;

            }

        }

        List<int[][]> areas = MakeAreas(arr);

        for (int[][] area : areas) {

            int first = area[0][0];

            boolean allSame = Arrays.stream(area)

                    .flatMapToInt(Arrays::stream)

                    .allMatch(n -> n == first);

            System.out.println("숫자: " + first + ", 모두 같음: " + allSame);

            if (!allSame) {

                System.out.println("모두불일치 영역 쪼개기");

                dfs(area, count, index + 1);

            } else {

                System.out.println("모두일치함");

                count.put(first, count.getOrDefault(first, 0) + 1);

            }

        }

    }

    public static List<int[][]> MakeAreas(int[][] arr) {

        System.out.println("MakeAreas");

        List<int[][]> areas = new ArrayList<>();

        int half = arr.length / 2;

        for (int row = 0; row < arr.length; row += half) {

            for (int col = 0; col < arr.length; col += half) {

                int[][] area = new int[half][half];

                for (int i = 0; i < half; i++) {

                    area[i] = Arrays.copyOfRange(arr[row + i], col, col + half);

                }

                areas.add(area);

            }

        }

        IntStream.range(0, areas.size()).forEach(i -> {

            System.out.println("영역 " + (i + 1));

            Arrays.stream(areas.get(i)).forEach(a -> System.out.println(Arrays.toString(a)));

        });

        System.out.println("-----------------------------");

        return areas;

    }

 

---

결과

---

gpt피드백

1. 알고리즘 평가

분할 정복 알고리즘 선택 적절

 

① 분할 정복을 정확하게 이해했어.

처음에는 작은 정사각형을 직접 찾아야 하는 것으로 생각했지만, 문제에서 정해진 4등분 규칙을 이해한 뒤 재귀로 해결했어.

알고리즘 개선점

개선 1. 배열을 실제로 복사하지 않아도 돼.

개선 2. 영역 전체 검사를 DFS 시작 부분으로 통일

개선 3. 시간 및 공간 복잡도

배열 한 변의 길이를 N이라고 할 때:

구분기존 알고리즘좌표 기반 개선

최악 시간 복잡도	O(N² log N)	O(N² log N)
추가 공간 복잡도	O(N²)	O(log N)
배열 복사	있음	없음
재귀 깊이	O(log N)	O(log N)

두 방식 모두 각 분할 단계에서 영역을 검사하기 때문에 최악의 시간 복잡도는 같아.

하지만 개선된 방식은 배열 복사가 없어 실제 실행 비용과 메모리 사용량을 줄일 수 있어

 

2. 코드 평가

가독성 양호, 불필요한 코드 존재

잘한 점

① 메서드를 분리했어.

각 메서드의 역할이 명확해.

• solution() : 결과 반환
• dfs() : 영역 검사 및 재귀
• MakeAreas() : 영역 분할

한 메서드에 모든 로직을 작성하는 것보다 유지보수하기 좋아.

코드 개선점

개선 1. arr.clone() 제거

개선 2. Map<Integer, Integer> 대신 int[]

개선 3. index 매개변수 제거

 

 

 

---

후기

2틀고민했다 왜?

내가 문제를 잘못이해했다

모든영억을 탐색해야하는줄 알았는데

결국 이게맞나 싶다가 gpt힌트를 받았는데

알고보니 각영역을 분할 규칙을 이미 문제에서 정해놨었다

젠장..문제의 요구조건을 처음에 제대로 이해못하면 이런일이 발생한다..