[프로그래머스][월간 코드 챌린지 시즌 1][C++] 쿼드압축 후 개수 세기

문제

프로그래머스 월간 코드 챌린지 시즌 1 - 쿼드압축 후 개수 세기 (Level 2)

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

 

---

문제 풀이

접근 방식

이 문제는 월간 코드 챌린지 시즌 1 (10월)의 2번 문제로,

주어진 배열을 쿼드 트리와 같은 방식으로 압축하여 0과 1의 개수를 구하는 문제이다.

구체적인 압축 방식은 다음과 같다.

 

쿼드 트리 방식

 

압축이 가능한 지 탐색할 영역의 한 변의 길이는 total_len에서 반으로 계속 나눠 1이 될 때까지 탐색해야하므로,

while문과 4중 for문으로 이 부분을 구현해주었다.

(아래의 코드에서 a와 b는 탐색 영역의 시작 위치를 의미한다.)

 

탐색할 범위를 설정한 후에는 탐색 범위 내의 값이 모두 같은 숫자로 이뤄졌는 지를 확인하여,

모두 같은 숫자일 경우에는 해당 숫자의 개수를 증가시키고 해당 범위의 숫자들을 -1로 바꿔주었고,

아닌 경우에는 해당 범위의 탐색을 종료해주었다.

 

이 방법 외에 DFS를 통해 구간을 나눠 탐색하는 방법도 있으나,

다중 for문을 통해 구현한 이 방법이 수행 시간이 더 짧았다.

 

---

풀이 코드 - C++

#include <vector>

using namespace std;

vector<int> solution(vector<vector<int>> arr) {
    vector<int> answer(2);
    int len = arr.size();
    int total = len;
    int idx = 0;
    while (len != 0) {
        for (int a = 0; a < total; a += len) {
            for (int b = 0; b < total; b += len) {
                bool check = true;
                int start = arr[a][b];
                if (start == -1) continue;
                for (int i = 0; i < len; i++) {
                    for (int j = 0; j < len; j++) {
                        if (start != arr[a + i][b + j]) {
                            check = false;
                            break;
                        }
                    }
                    if (!check) break;
                }
                if (check) {
                    answer[start]++;
                    for (int i = 0; i < len; i++) {
                        for (int j = 0; j < len; j++) {
                            arr[a + i][b + j] = -1;
                        }
                    }
                }
            }
        }

        len /= 2;
    }
    return answer;
}

실행 결과

실행 결과 : 통과 (100.0)