(c++) 프로그래머스 "쿼드압축 후 개수 세기"

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

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

---

나의 풀이

첫 풀이는 5,6,15,16에서 시간초과가 발생했다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> result;
void check(vector<vector<int>> arr, pair<int,int> start, int len) {
    if (len == 1) {
        result.push_back(arr[start.first][start.second]);
        return;
    }
    int last = arr[start.first][start.second];
    for (int i = 0; i < len; i++) {
        vector<int> tmp;
        auto begin = arr[start.first+i].begin() + start.second;
        tmp.assign(begin, begin + len);
        sort(tmp.begin(), tmp.end());
        if (tmp[0] != tmp[tmp.size() - 1] || tmp[0] != last) {
            check(arr, start, len / 2);
            check(arr, {start.first,start.second+len/2}, len / 2);
            check(arr, { start.first + len / 2 ,start.second}, len / 2);
            check(arr, { start.first + len / 2 ,start.second + len / 2 }, len / 2);
            return;
        }
    }
    result.push_back(last);
}

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer;
    check(arr, { 0,0 }, arr.size());
    sort(result.begin(), result.end());
    int one = find(result.begin(), result.end(), 1) - result.begin();
    answer.push_back(one);
    answer.push_back(result.size() - one);
    return answer;
}

---

완성된 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> list;
int result[] = { 0,0 };
void check(pair<int, int> start, int len) {
    if (len == 1) {
        result[list[start.first][start.second]]++;
        return;
    }
    int last = list[start.first][start.second];
    for (int i = start.first; i < start.first + len; i++) {
        for (int k = start.second; k < start.second + len; k++) {
            if (last != list[i][k]) {
                check(start, len / 2);
                check({ start.first,start.second + len / 2 }, len / 2);
                check({ start.first + len / 2 ,start.second }, len / 2);
                check({ start.first + len / 2 ,start.second + len / 2 }, len / 2);
                return;
            }
        }
    }
    result[last]++;
}

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer;
    list.assign(arr.begin(), arr.end());
    check({ 0,0 }, arr.size());
    return { result[0],result[1] };
}

 

제귀를 사용하는 문제라고 생각했는데 왜 시간초과가 뜨는지 의문이었다.

질문 게시판을 보다가 c++에서 vector인 매개변수를 넘겨줄때 주소를 넘기는 것이 아니라 복사를 하여 새로운 주소를 부여하기 때문에 시간적, 공간적으로 비용이 더 든다는 것을 알게됬다.

그래서 코드 때문인줄 알았던 첫번째 코드도 그러한 이유로 시간초과가 떴던 것이다.

첫번째 코드를 전역변수를 사용하도록 수정하고 소요된 시간을 보면 

두번째 코드(최대 : 6.12ms)

첫번째 코드(최대시간 : 12.63 ms)

확실히 정렬이 시간이 nlogn의 시간복잡도를 가지기 때문에 더 오래걸리는 것을 볼 수 있다.