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

Activity

1. CMSSKKK

   added

   Problem

   on Nov 30, 2022
2. CMSSKKK

   self-assigned this

   on Nov 30, 2022
3. CMSSKKK commented on Nov 30, 2022

   

   CMSSKKK

   on Nov 30, 2022

   MemberAuthor

   More actions

   풀이 언어

   • 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( )
4. seokho-ham

   removed

   Problem

   on Feb 20, 2023