[프로그래머스][C++] 쿼드압축 후 개수 세기

쿼드압축 후 개수 세기

문제 링크

쿼드압축 후 개수 세기

분석

쿼드트리 압축이란 주어진 배열이 모두 같은 숫자(0 또는 1)로 이루어져 있다면, 이를 하나로 압축하는 것입니다.
만약 압축 할 수 없다면, 배열을 4개의 동일한 크기의 부분으로 분할한 뒤, 각 부분을 재귀적으로 검사해야합니다.

쿼드압축 후 개수 세기로, 2차원 배열을 쿼드트리 방식으로 압축하면서 0과 1의 개수를 세는 문제입니다.

arr이라는 2차원 배열을 쿼드트리 방식으로 압축해야합니다.

이 문제를 해결하기 위해서는 재귀 함수(DFS)를 활용해 분할 정복 기법을 사용해야합니다.

1. 주어진 배열의 특정 영역이 모두 (0 또는 1)인지 확인합니다.
2. 만약 같은 숫자로 이루어져 있다면, 해당 숫자의 개수를 증가시키고 탐색을 종료합니다.
3. 그렇지 않다면, 배열을 4등분으로 균등하게 나누어 다시 탐색합니다.
4. 각 부분을 재귀적으로 검사해 0과 1의 개수를 반환합니다.

풀이

#include <vector>

using namespace std;

// 특정 구역이 모두 같은 숫자로 이루어졌는지 확인하는 함수
bool isUniform(const vector<vector<int>>& arr, int x, int y, int size)
{
    int first = arr[x][y];  // 시작점의 숫자

    // x부터 크기만큼 반복
    for (int i = x; i < x + size; ++i)
    {
        // y부터 크기만큼 반복
        for (int j = y; j < y + size; ++j)
        {
            // 만약 다른 숫자가 있는 경우
            if (arr[i][j] != first)
            {
                return false;
            }
        }
    }
    
    return true;
}

void compress(vector<int>& answer, const vector<vector<int>>& arr, int x, int y, int size)
{
    // 모두 같은 숫자로 이루어진 경우 해당 숫자의 개수를 증가
    if (isUniform(arr, x, y, size))
    {
        answer[arr[x][y]]++;
        return;
    }
    
    // 4등분을 위해 중간 크기를 가져옴
    int newsize = size / 2;
    
    // 각각 재귀 호출
    compress(answer, arr, x, y, newsize);   // 왼쪽 위
    compress(answer, arr, x, y + newsize, newsize); // 오른쪽 위
    compress(answer, arr, x + newsize, y, newsize); // 왼쪽 아래
    compress(answer, arr, x + newsize, y + newsize, newsize);   // 오른쪽 아래
}

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer(2, 0);
    
    // 전체 배열을 시작점으로 재귀 호출
    compress(answer, arr, 0, 0, arr.size());
    
    return answer;
}

isUniform 함수는 arr[x][y]를 기준으로 모든 값이 같은지 검사합니다.

compress 함수는 재귀적으로 배열을 나누고, 구역의 숫자가 모두 같다면 압축합니다.
만약 구역의 숫자가 모두 같다면 0 또는 1의 개수를 증가시키고 종료하게 되며, 해당 구역을 더이상 살펴보지 않으므로 압축한 결과입니다.
만약 구역의 숫자가 모두 다르다면 4등분으로 영역을 나눠 재귀호출하게 되며, 해당 구역들을 다시 살펴봅니다.

성능 요약

시간 복잡도는 $O(N^2 \ log \ N)$입니다.

• compress함수가 1번 호출되면 배열을 4등분 $O(1)$
• compress함수의 최대 깊이는 $O(log \ N)$
• isUniform함수의 검사 $O(N^2)$
• $O(N^2 + log \ N + 1)$

공간 복잡도는 $O(log \ N)$입니다.

• 재귀 호출 스택 $O(log \ N)$

테스트 1 〉 통과 (0.03ms, 4.14MB)
테스트 2 〉 통과 (0.02ms, 3.61MB)
테스트 3 〉 통과 (0.02ms, 4.21MB)
테스트 4 〉 통과 (0.02ms, 4.2MB)
테스트 5 〉 통과 (4.31ms, 13.5MB)
테스트 6 〉 통과 (1.92ms, 13.5MB)
테스트 7 〉 통과 (1.13ms, 13.4MB)
테스트 8 〉 통과 (0.82ms, 13.4MB)
테스트 9 〉 통과 (1.13ms, 13.5MB)
테스트 10 〉 통과 (3.08ms, 40.3MB)
테스트 11 〉 통과 (0.01ms, 4.24MB)
테스트 12 〉 통과 (0.01ms, 4.22MB)
테스트 13 〉 통과 (0.88ms, 13.5MB)
테스트 14 〉 통과 (3.75ms, 40.4MB)
테스트 15 〉 통과 (3.91ms, 40.4MB)
테스트 16 〉 통과 (1.00ms, 13.5MB)