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

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

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

 

문제접근법 : arr의 2차원인 2^n*2^n 배열이기때문에 반드시 가로세로 2등분해서 총4조각을 만들수잇습니다. 배열이 하나가될때까지 가능하기때문에 자기자신의 기준인 y,x좌표의 기준으로 size까지 같은지 확인하면 나누지않고 그안에있는 0또는 1의 개수를 새기만하면되고 같지않으면 나누면 되기때문에  분할정복문제인 재귀함수를 이용하면 쉽게풀리는 문제입니다.

 

소스코드 :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

//By 콩순이냉장고 #include<bits/stdc++.h> using namespace std;    int ans[2] = { 0 }; bool check(int y,int x,int size, vector<vector<int>>& arr) {     int t = arr[y][x];     for (int i = y; i < y + size; i++) {         for (int j = x; j < x + size; j++) {             if (arr[i][j] != t)                 return true;         }     }     return false; } void  split(int y,int x,int size, vector<vector<int>> &arr) {     if (check(y, x, size, arr)) {         split(y, x, size / 2, arr);         split(y, x + size / 2, size / 2, arr);         split(y + size / 2, x, size / 2,arr);         split(y + size / 2, x + size / 2, size / 2, arr);     }     else {         ans[arr[y][x]]++;     }   } vector<int> solution(vector<vector<int>> arr) {     split(0, 0, arr.size(), arr);     return vector<int>{ans[0], ans[1]}; } Colored by Color Scripter

cs

 

궁금한점 혹은 모르는점이나 논리적인 오류지적등 어떤 질문이든 댓글은 언제나 환영입니다.