프로그래머스 Level 2 : 쿼드압축 후 개수 세기 C언어

▶문제 : 코딩테스트 연습 - 쿼드압축 후 개수 세기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

▶코드 작성

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int** ary;
int count[2];//[0] : 0 , [1] : 1

void func(int left, int right, int top, int bottom){
    int zero=0,one=0;
    for(int i=top;i<=bottom;i++){//주어진 범위안의 0,1개수 구하기
        for(int j=left;j<=right;j++){
            if(ary[i][j]) one++;
            else zero++;
        }
    }

    if(zero==0) count[1]=count[1]-one+1;//주어진 칸이 모두 1일 때 압축
    else if(one==0) count[0]=count[0]-zero+1;//주어진 칸이 모두 0일 때 압축
    else{
        if(right-left==1) return;//칸이 2x2라면 종료
        int midW=left+(right-left)/2;//가로의 중간값
        int midH=top+(bottom-top)/2;//세로의 중간값
        func(left,midW,top,midH);//왼쪽 위
        func(left,midW,midH+1,bottom);//왼쪽 아래
        func(midW+1,right,top,midH);//오른쪽 위
        func(midW+1,right,midH+1,bottom);//오른쪽 아래
    }
}

int* solution(int** arr, size_t arr_rows, size_t arr_cols) {
    int* answer = (int*)malloc(sizeof(int) * 2);//[0] : 0 , [1] : 1
    ary=arr;

    for(int i=0;i<arr_rows;i++){//모든 1과 0의 개수를 구하기
        for(int j=0;j<arr_cols;j++){
            if(arr[i][j]) count[1]++;
            else count[0]++;
        }
    }

    func(0,arr_rows-1,0,arr_cols-1);
    answer[0]=count[0];//0개수 대입
    answer[1]=count[1];//1개수 대입

    return answer;
}

 

▶해석

재귀함수를 이용해 주어진 칸 전체가 0 또는 1이 아니라면 4등분으로 나누어 다시 구하도록 작성하였다.

0과 1의 개수는 먼저 0과 1의 총 개수를 count배열에 저장한 뒤 func함수에서 0 또는 1로 압축할 수 있을 때 그 개수를 count배열에서 빼고 +1 하면 하나로 압축하게 되는 것이다.