전형적인 D&C 문제라 간단히 풀었으나 처음 제출했을 때는 시간초과가 났다. 이것보다는 더 빠른 로직를 생각해낼 수 없어 이것저것 시도해 본 결과 통과했다..!
문제는 매개변수로 arr를 주는 방식에 있었다. 처음에는 그냥 vector<vector<int>> arr처럼 값으로 전달(pass by value)해주어 인자의 복사본을 전달했다. D&C에서는 함수를 재귀적으로 계속 호출하는데 함수를 호출할 때 마다 인자를 복사하는데 시간이 많이 걸려 시간초과가 발생하였다.
그래서 값에 의한 전달 대신 참조로 전달 (pass by reference) 했더니 제한 시간 내에 통과되는 것을 확인했다. 참조자 &를 사용해 const vector<vector<int>>& arr처럼 선언하면 이것은 원래의 vector<vector<int>> arr의 별명이 되어 같은 메모리를 공유한다. 그래서 새로 메모리를 할당하지 않기 때문에 시간적, 공간적으로도 훨씬 더 효율적이다.
C++에서 전달은 값에 의한 전달 참조에 의한 전달 외에도 주소에 의한 전달이 있는데 이는 포인터를 사용해 전달하는 방식을 말한다. 여기저기서 같은 인자를 호출하는 경우 원하지 않는 결과 발생할 수 있기 때문에 조심해서 써야 하지만, 이 문제에서는 arr 값을 직접 변경하지 않고 그냥 읽기만 하므로 안심하고(ㅋㅋ)썼다. 그리고 값이 변경되지 않도록 const 까지 붙여줬음 😎
#include <vector>
using namespace std;
int zeros, ones;
bool check(const vector<vector<int>>& arr, int row, int col, int size) {
int start = arr[row][col];
int i, j;
for (i = row; i < row + size; i++) {
for (j = col; j < col + size; j++) {
if (arr[i][j] != start) return false;
}
}
return true;
}
void divide(const vector<vector<int>>& arr, int row, int col, int size) {
if (size <= 1 || check(arr, row, col, size)) {
arr[row][col] ? ones++ : zeros++;
return;
}
divide(arr, row, col, size / 2);
divide(arr, row, col + size / 2, size / 2);
divide(arr, row + size / 2, col, size / 2);
divide(arr, row + size / 2, col + size / 2, size / 2);
}
vector<int> solution(vector<vector<int>> arr) {
vector<int> answer;
divide(arr, 0, 0, arr.size());
answer.push_back(zeros);
answer.push_back(ones);
return answer;
}