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

쿼드 압축 후 개수 세기 (Level 2)

문제

전체 문제 보기

코딩테스트 연습 - 쿼드압축 후 개수 세기

접근법

이 문제는 다음과 같이 분할 정복으로 풀 수 있는 문제입니다.

• 2차원 배열에 모든 값을 탐색하여 압축 가능한지 확인한다.
  • 압축이 불가능 하다면, 1 사분면, 2 사분면, 3 사분면, 4 사분면으로 나누고 각각 다시 압축이 가능한지 확인한다.
  • 압축이 가능 하다면, 압축된 수의 카운트를 1 증가시키고 함수를 반환한다.

전체 소스 코드

• Check 함수: 입력 받은 2차원 배열이 압축 가능하다면 true, 불가능하다면 false를 반환합니다.
• Division 함수: Check 함수를 사용하여 압축 가능한지 확인한 후, 압축 불가능하다면 구간을 나눠 Division 함수를 재귀 호출합니다.

#include <string>
#include <vector>
using namespace std;

bool Check(vector<vector<int>>& arr, int x, int y, int size)
{    
    int startNumber = arr[x][y];

    for(int i = x; i < x + size; ++i)
    {
        for(int j = y; j < y + size; ++j)
        {
            if(arr[i][j] != startNumber)
                return false;
        }
    }
    return true;
}

void Division(vector<int>& answer, vector<vector<int>>& arr, int x, int y, int size)
{
    int startNumber = arr[x][y];
    if(Check(arr, x, y, size))
    {
        answer[startNumber]++;
        return;
    }
    int half = size / 2;
    // 1사분면
    Division(answer, arr, x, y, half);
    // 2사분면
    Division(answer, arr, x + half, y, half);
    // 3사분면
    Division(answer, arr, x, y + half, half);
    // 4사분면
    Division(answer, arr, x + half, y + half, half);

}

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer;
    answer.resize(2);
    Division(answer, arr, 0, 0, arr.size());
    return answer;
}

성능 평가

2차원 배열의 최대 크기(총원소의 개수)를 \(N\)이라고 했을 때 전체 시간 복잡도는 \(N\mbox{log}N\) 입니다. 왜냐하면 재귀 함수의 호출 깊이는 \(\mbox{log}N\) 이며 각 깊이마다 총 원소 \(N\)개를 모두 탐색하기 때문입니다. 공간 복잡도는 전체 원소를 저장하기 위한 \(O(N)\) 만큼의 공간이 필요합니다.