프로그래머스 - 쿼드압축 후 개수 세기

프로그래머스 - 쿼드압축 후 개수 세기

아 이거 자꾸 시간초과나서 뭔가 잘못했나하고 봤는데, 지금까지 습관적으로 읽기전용 벡터를 const만 붙여서 함수인자로 넣어주고 있었다;;
cpp에서 &를 붙이지 않으면 함수인자로 전달할 때 메모리 카피를 하는데, 이거 때문에 테스트케이스 5, 16번에선 시간초과가 발생했고, 그 외에도 다 엄청 느렸다... 좀 큰 실수인 것 같은데, 지금까지 코테볼때도 계속 이랬다;;
그냥 맘편하게 전역변수 쓰는게 좋을 것 같다..

일단 문제는 쉬운 편인데, 위 처럼 8, 4, 2, 1 등등 2의 지수승을 가진 정사각형안의 숫자가 모두 같다면 해당 부분을 압축하는 것이다. 이 과정을 주어진 벡터의 size 부터 1까지 해주면 된다.
주어진 quad에서 row_start, col_start를 잘 찾아서 row_start ~ row_start + quad, col_start ~ col_start + quad 까지 숫자가 같은지 check해주면 된다.

구현 방식은 재귀로 풀어도 되고, 그냥 iter 돌면서 quad가 2일때까지 돌아줘도 된다. (아주 살짝 최적화)

먼저 재귀없이 그냥 iteration을 돌면서 푼 코드이다.
각 quad에서 row, col이 순차적으로 증가하기 때문에 visitMap을 관리했는데, 재귀로 구현하면 visitMap이 필요없다.

#include <string>
#include <vector>

using namespace std;

int visit[1024][1024];
vector<int> answer(2, 0);

const inline bool check(int row, int col, int quad, const vector<vector<int>> &map)
{
    int row_end = row + quad;
    int col_end = col + quad;
    int num = map[row][col];
    for(int i=row; i<row_end; i++) 
        for(int j=col; j<col_end; j++) 
            if(map[i][j] != num) 
                return false;
    
    return true;
}
void check_visit(int row, int col, int quad)
{
    int row_end = row + quad;
    int col_end = col + quad;
    for(int i=row; i<row_end; i+=2) 
        for(int j=col; j<col_end; j+=2) 
            visit[i][j] = 1;
}

vector<int> solution(vector<vector<int>> arr) {
    int size = arr.size();
    int quad = size;
    
    while(1) {
        if(quad == 0)
            break;
        
        int row_start = 0, col_start = 0;
        int row_end = size, col_end = size;
        int row_box_num = (size / quad);
        int iter_end = row_box_num * row_box_num;
        int idx = 0;
        for(int iter = 0; iter<iter_end; iter++) {
            idx = iter * quad;
            row_start = (int)(idx / size) * quad;
            col_start = idx % size;
            row_end = row_start + quad;
            col_end = col_start + quad;
            
            if(visit[row_start][col_start] == 0) {
                if(check(row_start, col_start, quad, arr)) {
                    answer[arr[row_start][col_start]]++;
                    check_visit(row_start, col_start, quad);
                } else {
                    if(quad == 2) {
                        for(int i=row_start; i<row_end; i++) {
                            for(int j=col_start; j<col_end; j++) {
                                answer[arr[i][j]]++;
                            }
                        }
                    }
                }
            }
        }
        if(quad == 2)
            break;
        
        quad >>= 1;
    }
    
    return answer;
}

다음은 재귀 코드이다. 위 코드에 비해서 코드가 간결하다.

#include <string>
#include <vector>

using namespace std;

int visit[1024][1024];
vector<int> answer(2, 0);

const inline bool check(int row, int col, int quad, const vector<vector<int>> &map)
{
    int row_end = row + quad;
    int col_end = col + quad;
    int num = map[row][col];
    for(int i=row; i<row_end; i++) 
        for(int j=col; j<col_end; j++) 
            if(map[i][j] != num) 
                return false;
    
    return true;
}

int rowDir[4] = { 0, 0, 1, 1 };
int colDir[4] = { 0, 1, 0, 1 };
void func(int row, int col, int quad, const int size, const vector<vector<int>> &map)
{
    if(check(row, col, quad, map) || quad == 1) {
        answer[map[row][col]]++;
        return;
    }
    
    int nrow, ncol, nquad = quad >> 1;
    for(int i=0;i<4;i++) {
        nrow = row + rowDir[i] * nquad;
        ncol = col + colDir[i] * nquad;
        func(nrow, ncol, nquad, size, map);
    }
}
vector<int> solution(vector<vector<int>> arr) {
    int size = arr.size();
    int quad = size;
    
    func(0, 0, quad, size, arr);
    
    return answer;
}

visitMap 관리하면서 iteration 방식으로 푼 결과이다.

재귀로 푼 결과이다.

재귀가 코드도 깔끔하고 성능도 좋은 것 같다.