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

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/131703?language=java

문제 풀이

• 브루트 포스로 풀이할 경우 시간초과 발생하진 않을 것 같지만..? 좀 더 효율적으로 풀이하였다.
• 생각한 풀이는 다음과 같다.

  1. 열을 뒤집는 작업을 비트마스킹을 사용하여 brute force를 진행한다. (최대 1024회)
  2. 뒤집기가 완료되면 행을 순회하며 정답 여부를 확인하는데
     - 해당 행의 모든 수가 target과 같으면 맞다고 판별하고 넘어감
     - 해당 행의 모든 수가 target과 다르면 맞다고 판별하고 뒤집기 횟수 +1 하고 넘어감

소스 코드 (JAVA)

import java.util.Arrays;

class Solution {
    public int R, C;
    public int[][] M, T, tmp;

    public void flipCol(int c) {
        for (int i = 0; i < R; i++)
            tmp[i][c] = tmp[i][c] == 0 ? 1 : 0;
    }

    public void copyArr() {
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                tmp[i][j] = M[i][j];
    }


    public int solution(int[][] beginning, int[][] target) {
        R = beginning.length;
        C = beginning[0].length;
        M = beginning;
        T = target;
        tmp = new int[R][C];
        int result = Integer.MAX_VALUE;
        //모든 열에 대해서 반복
        for (int mask = 0; mask < 2 << C; mask++) {
            int tmpResult = 0;
            copyArr();
            //1. 칼럼 뒤집기
            for (int col = 0; col < C; col++) {
                //뒤집지 않는 열의 경우 냅둠
                if ((mask & 2 << col) == 0) continue;
                tmpResult++;
                flipCol(col);
            }
            //2. 모든 로우 판별
            boolean flag = false;
            for (int i = 0; i < R; i++) {
                if (flag) break;
                //안뒤집어져 있으면
                if (tmp[i][0] == T[i][0]) {
                    for (int j = 1; j < C; j++) {
                        if (tmp[i][j] != T[i][j]){
                            flag = true;
                            break;
                        }
                    }
                }
                //뒤집어져 있으면
                else {
                    for (int j = 1; j < C; j++) {
                        if (tmp[i][j] == T[i][j]){
                            flag = true;
                            break;
                        }
                    }
                    if (!flag) tmpResult++;
                }
            }
            //일치하는 경우
            if (!flag) result = Math.min(result, tmpResult);
        }
        if (result == Integer.MAX_VALUE) return -1;
        else return result;
    }
}