[Algorithm] 프로그래머스 쿼드압축 후 개수 세기 c++ (시간초과)

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

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

 

풀이

재귀(분할 정복)

• 2차원 벡터를 탐색하면서 내부의 수가 같은지 다른지 확인해야 함
• 정사각형이므로 좌측상단의 좌표(x,y)와 현재 길이(n)만 알면 탐색 가능
• 모두 같은 수가 아닐 때 4등분으로 나누어 각각 다시 탐색

 

주의
처음에 계속 시간초과가 발생했다. 코드를 보고 또 봐도 문제가 없는 것 같은데 시간초과가 발생해서 찾아보니 2차원 vector를 함수의 인자로 넘기는 부분이 원인이였다.

 

초기 코드

vector를 값으로 넘기면 재귀 함수가 호출되면서 그 값을 계속 복사하기 때문에 시간초과 발생

void qt(int x, int y, int n, vector<vector<int>> arr)

 

수정 코드

참조로 넘겨야 재귀 함수가 계속 호출되더라도 시간초과가 발생하지 않음

void qt(int x, int y, int n, vector<vector<int>> &arr)

 

소스코드

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

int zero, one;

void qt(int x, int y, int n, vector<vector<int>> &arr){
    int cur = arr[x][y];
    if(n == 1){
        if(cur) one++;
        else zero++;
        return;
    }    

    bool flag = true;
    for(int i=x; i<x+n; i++){
        for(int j=y; j<y+n; j++){
            if(cur != arr[i][j]){
                flag = false;
                break;
            }
        }
        if(!flag) break;
    }

    if(flag){
        if(cur) one++;
        else zero++;
        return;
    } 

    int mid = n/2;
    qt(x, y, mid, arr);
    qt(x, y+mid, mid, arr);
    qt(x+mid, y, mid, arr);
    qt(x+mid, y+mid, mid, arr);
}

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer;
    qt(0, 0, arr.size(), arr);
    answer.push_back(zero);
    answer.push_back(one);
    return answer;
}