[코딩테스트] 프로그래머스 - 쿼드압축 후 개수 세기(Java, Level2)

안녕하세요~

오늘은 해결 못할 줄 알았지만 운좋게 해결한~ 문제!

 

기분좋게 잠들 수 있을것만 같습니다~

문제 바로 만나보시죠!

https://school.programmers.co.kr/learn/courses/30/lessons/68936

프로그래머스

 

다음은 제가 작성한 코드입니다.

요령이 없다보니 코드가 깁니다... 아마 더 효율좋은 코드가 많이 있을거같으니~ 같이 참조해보시며 좋은것만 쏙쏙뽑아가시면 되겠습니다.

class Solution {
    int total1;
    int total0;
    int checker_result;
    int[] answer;
    public int[] solution(int[][] arr) {
        total1=0;
        total0=0;
        checker_result=0;
        answer= new int[2];
        
        checker_result=checker(arr);
        if(checker(arr)==-1)
        {
            dfs(arr);
            answer[0]=total0;
            answer[1]=total1;
        }
        else
        {
            if(checker_result==1)
            {
                answer[0]=0;
                answer[1]=1;
            }
            else if(checker_result==0)
            {
                answer[1]=0;
                answer[0]=1;
            }           
        }
        
        
        
        return answer;
    }
    public void dfs(int[][] arr)
    {
        if(arr.length==1)
        {
            if(arr[0][0]==1)
                total1=total1+1;
            else
                total0=total0+1;
            return;
        }
        int arrlength=arr.length/2;
        
        // 1번째 파트
        int[][]arr1=new int[arrlength][arrlength];
        for(int i=0;i<arr.length/2;i++)
        {
            for(int j=0;j<arr.length/2;j++)
            {
                arr1[i][j]=arr[i][j];
            }
        }
        checker_result=checker(arr1);
        if(checker_result==-1)
            dfs(arr1);
        else
        {
            if(checker_result==1)
                total1++;
            else if(checker_result==0)
                total0++;       
        }
        
        // 2번째 파트
        int[][]arr2=new int[arrlength][arrlength];
        for(int i=0;i<arr.length/2;i++)
        {
            for(int j=0;j<arr.length/2;j++)
            {
                arr2[i][j]=arr[i+arr.length/2][j];
            }
        }
        checker_result=checker(arr2);
        if(checker_result==-1)
            dfs(arr2);
        else
        {
            if(checker_result==1)
                total1++;
            else if(checker_result==0)
                total0++;       
        }
        // 3번째 파트
        int[][]arr3=new int[arrlength][arrlength];
        for(int i=0;i<arr.length/2;i++)
        {
            for(int j=0;j<arr.length/2;j++)
            {
                arr3[i][j]=arr[i][j+arr.length/2];
            }
        }
        checker_result=checker(arr3);
        if(checker_result==-1)
            dfs(arr3);
        else
        {
            if(checker_result==1)
                total1++;
            else if(checker_result==0)
                total0++;       
        }
        
        
        // 4번째 파트
        int[][]arr4=new int[arrlength][arrlength];
        for(int i=0;i<arr.length/2;i++)
        {
            for(int j=0;j<arr.length/2;j++)
            {
                arr4[i][j]=arr[i+arr.length/2][j+arr.length/2];
            }
        }
        checker_result=checker(arr4);
        if(checker_result==-1)
            dfs(arr4);
        else
        {
            if(checker_result==1)
                total1++;
            else if(checker_result==0)
                total0++;       
        }
        
    }
    
    public int checker(int[][]arr)
    {
        int one_count=0;
        int zero_count=0;
        
        for(int i=0;i<arr.length;i++)
        {
            for(int j=0;j<arr[0].length;j++)
            {
                if(arr[i][j]==0)
                    zero_count++;
                else if(arr[i][j]==1)
                    one_count++;;
                
                if(zero_count!=0&&one_count!=0)
                    return -1;
            }
        }
        if(zero_count==0&&one_count>0)
            return 1;
        else if(zero_count>0&&one_count==0)
            return 0;
        return -1;
    }
}

오우 생각보다 코드가 기네요...

이제 제가 생각한 로직에 대해 말씀드리겠습니다.

 

저는 이문제를 보자마자 생각이 든건 아 이거는 DFS로 풀어야겠다! 입니다.

그래서 먼저 함수부분으로 보자면

0) 전역변수

    - total1은 1로구성된 총 갯수를, total0은 0으로 구성된 총 갯수입니다.

    - checker_result 변수는 checker의 결과에 따라서 dfs를 할지 return할지 결정합니다.

1) Solution 함수

    - 입력받은 arr이 모두 1 or 0으로 구성돼 있는지 확인 후 dfs에 arr을 전달하는 역할

    - 만약 1or 0으로만 arr이 구성돼 있다면 처리 후 answer를 리턴하는 역할입니다.

2) DFS함수

    - 입력받은 arr의 길이가 1인지 검사하고 1이라면 total1, total0에 해당하는 값을 ++해주고 return합니다.

    - 1보다 크다면 가로, 세로 /2를 합니다. 그렇게해서 총 4개의 파트로 나눠 각각이 또 dfs를 태워줍니다. 

    - 사각형 가로세로 반으로 자른 사각형의 가로세로 반으로 자른 사각형의~ 이런식으로 생각하시면 되겠습니다.

3) Checker 함수

    - checker에서는 입력받은 arr을 검사합니다.

    - checker가 1과 0으로 둘 다 구성돼있는 순수하지 못한 arr이라면 -1을 리턴해 dfs를 태우도록하고

    - checker가 1혹은 0으로만 구성돼 있는 순수한 arr이라면 해당 숫자를 리턴해 total1 혹은 total0이 처리하도록 했습니다.

 

효율성이 나는 코드인지는 좀 더 생각이 필요하겠습니다~ 아마 bfs?로도 가능할지는 생각을 저역시도 해봐야겠네요~

 

오늘은 여기까지 입니다.

감사합니다. :D