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

[CMSSKKK]

TITLE

2차원 동전 뒤집기

LINK

• 문제 출처 사이트 : 프로그래머스
• Link

📷 Screenshots

댓글 양식

• 아래 양식을 복사한 뒤 [shift]+[tab] 2회를 하고 작성하여 주세요

    ### 풀이 언어

    - python/java

    ### 코드

    ```python/java

    ```

    ### 핵심 로직 혹은 자료구조

    - 

    ### 시간 복잡도

    - O(  )

[CMSSKKK]

풀이 언어

• java

코드

class Solution {

    private int[][] allFlipped;
    private int[][] tempArr;
    private int row;
    private int col;

    public int solution(int[][] beginning, int[][] target) {
        int answer = Integer.MAX_VALUE;
        row = beginning.length;
        col = beginning[0].length;

        allFlipped = new int[row][col];
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                allFlipped[i][j] = 1 - beginning[i][j];
            }
        }

        int cnt = 0;
        for(int i = 0; i < 1 << row; i++) {

            tempArr = new int[row][col];
            int count = 0;

            for(int j = 0; j < row; j++) {

                int temp = 1 << j;
                int and = i & temp;
                if(and == 0) {
                    tempArr[j] = beginning[j].clone();
                } else {
                    tempArr[j] = allFlipped[j].clone();
                    count += 1;
                }
            }

            for(int k = 0; k < col; k++) {
                for(int t = 0; t < row; t++) {
                    if(target[t][k] != tempArr[t][k]) {
                        flipCol(k);
                        count++;
                        break;
                    }
                }
            }

            if(check(tempArr, target)) {
                answer = Math.min(count, answer);
            }
        }


        if(answer == Integer.MAX_VALUE) {
            return -1;
        }
        return answer;
    }


    private void flipCol(int targetCol) {

        for(int i = 0; i < row; i++) {
            tempArr[i][targetCol] = 1 - tempArr[i][targetCol];
        }

    }

    private boolean check(int[][] arr, int[][] target) {
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(arr[i][j] != target[i][j]) {
                    return false;
                };
            }
        }
        return true;
    }
}

핵심 로직 혹은 자료구조

시간 복잡도

• O( )