[programmers] 2차원 동전 뒤집기

06 Dec 2022 in Algorithm on Algorithm

• 링크
• 주의 사항
• 풀이 방법

링크

Link

주의 사항

• 처음 풀이때 행 > 열, 열 > 행 순으로 뒤집기를 시도 하여 가장 작은 값을 리턴하는 방식으로 풀이 함.
• 히든 테스트 2개가 안풀렸고 결국 모든 경우의 수를 계산하는 방식으로 풀이 함.

풀이 방법

1. 비트 연산자를 통해 행의 모든 경우의 수를 구한다.
   1. 1이 나온 행만 뒤집는다.
   2. rowMask < (1 « n) 의 조건으로 행의 모든 경우의 수를 표현 한다.
   3. ex) n이 3일 경우 = 001 (1): 첫 번째 행을 뒤집음, 010 (2): 두 번째 행을 뒤집음, 011 (3): 첫 번째와 두 번째 행을 뒤집음…
2. (rowMask & (1 « i)) != 0 조건으로 1이 나온 행을 뒤집는다.
   1. &은 각 자리의 1인 경우만 1로 연산한다. 5(101) & 4(100) = 4(100) 이므로 != 0 조건에 부합한다.

import java.util.Arrays;

class Solution {
    public static int solution(int[][] beginning, int[][] target) {
        int n = beginning.length;
        int m = beginning[0].length;
        int minFlips = Integer.MAX_VALUE;

        for (int rowMask = 0; rowMask < (1 << n); rowMask++) {
            int[][] flipped = new int[n][m];
            for (int i = 0; i < n; i++) {
                flipped[i] = Arrays.copyOf(beginning[i], m);
            }

            // Apply row flips based on rowMask
            for (int i = 0; i < n; i++) {
                if ((rowMask & (1 << i)) != 0) {
                    flipRow(flipped, i);
                }
            }

            int colMask = 0;
            for (int j = 0; j < m; j++) {
                if (flipped[0][j] != target[0][j]) {
                    flipCol(flipped, j);
                    colMask++;
                }
            }

            boolean match = true;
            for (int i = 1; i < n; i++) {
                if (!Arrays.equals(flipped[i], target[i])) {
                    match = false;
                    break;
                }
            }

            if (match) {
                minFlips = Math.min(minFlips, Integer.bitCount(rowMask) + colMask);
            }
        }

        return minFlips == Integer.MAX_VALUE ? -1 : minFlips;
    }

    private static void flipRow(int[][] matrix, int row) {
        for (int j = 0; j < matrix[row].length; j++) {
            matrix[row][j] = 1 - matrix[row][j];
        }
    }

    private static void flipCol(int[][] matrix, int col) {
        for (int i = 0; i < matrix.length; i++) {
            matrix[i][col] = 1 - matrix[i][col];
        }
    }
}