[JAVA] 프로그래머스 LEVEL3 2차원 동전 뒤집기

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

프로그래머스

코딩테스트 연습 > 연습문제 > 2차원 동전 뒤집기

 

난이도: LEVEL3

알고리즘 유형: 백트래킹 + 구현  

문제 접근

문제 요구사항을 그대로 구현만 하면 나오는 시간 복잡도는 2^N(1~10) * 2^N(1~10)이다.

하지만 해당 시간 복잡도는 문제를 시간 초과로 통과하지 못한다.

 

시간 복잡도를 2^N으로 바꾸는 방법이 있다. 

먼저 행을 기준으로 모든 경우의 수를 구한다.

해당 행을 기준으로 모든 열의 경우의 수를 구하는 게 아닌 

바로 검증을 통해서 끝내는 거다. 

 

검증 방법

모든 열에 대해서 해당 열이 뒤집어서 만들 수 있는 케이스인지 검증한다

만약 뒤집어서 만들 수 있으면 count 증가 다음 열 검증으로 넘어간다. 

해당 열의 모든 값이 최종 열의 값들과 같으면 뒤집을 필요 없으니 count는 증가시키지 않는다.

public static void check(int cnt){
    int count = 0;
    for(int i = 0; i < m; i++){
        int same = 0;
        int notSame = 0;
        for(int j = 0; j < n; j++){
            if(b[j][i] == t[j][i]) same++;
            else notSame++;
        }
        if(same == n) continue; // 전부 같으면 뒤집기 필요 x
        if(notSame == n){ // 전부 다르면 뒤집기 필요 o
            count++;
            continue;
        }
        return; // 어떤 부분은 같고 어떤 부분은 다르면 이번 케이스 불가능 
    }
    answer = Math.min(answer, cnt + count);
}

정답 코드 

import java.util.*;
class Solution {
    static int [][] t;
    static int [][] b;
    static int answer = Integer.MAX_VALUE;
    static int n,m;
    public int solution(int[][] beginning, int[][] target) {
        t = target;
        b = beginning;
        n = beginning.length; m = beginning[0].length;
        func(0, 0); // 행 뒤집기 경우의 수 백트래킹
        return answer == Integer.MAX_VALUE ? -1 : answer;
    }
    public static void check(int cnt){
        int count = 0;
        for(int i = 0; i < m; i++){
            int same = 0;
            int notSame = 0;
            for(int j = 0; j < n; j++){
                if(b[j][i] == t[j][i]) same++;
                else notSame++;
            }
            if(same == n) continue; // 전부 같으면 뒤집기 필요 x
            if(notSame == n){ // 전부 다르면 뒤집기 필요 o
                count++;
                continue;
            }
            return; // 어떤 부분은 같고 어떤 부분은 다르면 이번 케이스 불가능 
        }
        answer = Math.min(answer, cnt + count);
    }
    public static void func(int depth, int cnt){
        if(depth == n){
            check(cnt);
            return;
        }
        change(depth);
        func(depth + 1, cnt + 1); // 이번 행 뒤집기 o
        change(depth);
        func(depth + 1, cnt);     // 이번 행 뒤집기 x
    }
    // 행 뒤집기 
    public static void change(int row){
        // 0 -> 1 / 1 -> 0
        for(int i = 0; i < m; i++){
            b[row][i] = (b[row][i] + 1) % 2;
        }
    }
}