[Programmers] 프로그래머스 Lv.3 2차원 동전 뒤집기 문제풀이(C++)

핵심

1. beginning과 target의 xor연산으로 같은 값(1)과 다른 값(0)을 표현한 후, 이걸 모두 1로 만드는 문제로 재정의

2. 기준 줄을 가로로 설정하면(세로도 상관없음),  각 가로줄이 모두 Flip을 통해 기준 줄이 될 수 있어야 함 

    - 2번이 성립 안하면 목표 상태를 만들 수 없음

저는 이 두가지를 떠올려서 해결했습니다!

 

문제는 코드 아래에 있습니다.

#include <string>
#include <vector>
 
using namespace std;
/*
<문제>
동전을 행, 열 단위로 한꺼번에 뒤집어서 원하는 동전 배열 만들기
필요한 최소 뒤집기 수 구하기
 
동전들의 초기상태 2차원 정수배열 beginning, 목표상태인 target이 주어졌을 때
필요한 동전뒤집기 횟수 최솟값 return
목표상태를 만들지 못하는 경우 -1 return
 
beginning길이(=target길이) <= 10
beginning[i]길이 <= 10
beginning, target [i][j]는 각각 (i+1, j+1)의 동전 상태를 나타내며, 0은 앞면, 1은 뒷면 의미
 
<풀이>
beginning과 target의 차이를 먼저 파악 -> xor 연산한 결과 저장
 -> 이 결과에 적절히 뒤집기 연산해서 모두 1로 만들면 되는 거
 
가로줄 뒤집기를 통해 각 가로줄이 모두 같아질 수 있어야 함 / 아니면 목표상태 못만드는 거
가로, 세로 어떤 걸 기준으로 해도 수는 똑같음 / 단, 가로줄에서 가능한 형태가 2가지가 나옴
 
 
 -> 먼저, beginning과 target xor연산 - O(10*10)
    가로줄을 뒤집어가며 하나의 형태로 만들기 - O(10*10)
      형태가 다른데, 뒤집어도 같은형태가 안나오면 -1 return
    모든 가로줄을 뒤집어서 같은 형태로 만들었으면
      0 1을 보면서 세로줄 뒤집기  - O(10)
    뒤집기 카운트 return  
 
* 가로줄의 형태 기준이 2가지가 있음 -> 이 두가지 케이스를 모두 비교해봐야 함
 
    
<시간>
 O(n^2)이나, n이 10이라 가능할 듯
*/
 
//각 벡터 값이 같은지(true) 다른지(false)를 반환
bool compareGaro(vector<int> standard, vector<int> xor_res){
    for(int j=0; j<standard.size(); j++)
        //각 요소 비교
        if(standard[j]!=xor_res[j])
            return false;    
    return true;
}
 
//뒤집기 연산
vector<int> Flip(vector<int> a){
    for(int i=0; i<a.size(); i++)
        if(a[i]==0) a[i]=1; else a[i]=0;    
    return a;
}
 
//정답 구하는 함수
int getAnswer(int garo, int sero, vector<int> standard, vector<vector<int> > xor_res, int answer){
    //모든 가로줄을 뒤집어가며 동일한 형태로 바꾸기
    for(int i=1; i<sero; i++){
        
        //가로줄을 뒤집어가며 하나의 형태로 만들기
        bool flag = compareGaro(standard, xor_res[i]);    
        
        //첫줄과 같지 않은 경우
        if(flag==false){
            //뒤집기(카운트 증가)
            xor_res[i] = Flip(xor_res[i]); answer++;
            
            //뒤집어도 첫줄과 다르면 불가능한 경우
            if(compareGaro(standard, xor_res[i])==false) return -1;
        }
    }
    
    //이제 세로 뒤집기 카운트하면 됨
    for(int i=0; i<garo; i++)
        if(standard[i]==0) answer++;
    return answer;
}
 
 
int solution(vector<vector<int>> beginning, vector<vector<int>> target) {
    int answer = 0;
    vector<vector<int>> xor_res;    //xor연산결과
    
    //xor연산결과 생성
    for(int i=0; i<target.size(); i++){
        vector<int> a;
        for(int j=0; j<target[0].size(); j++){
            if(beginning[i][j]==target[i][j]) a.push_back(1);
            else a.push_back(0);
        }
        xor_res.push_back(a);
    }
    
    int sero = target.size(), garo = target[0].size();  //가로세로 길이
    
    vector<int> standard = xor_res[0]; //첫 줄이 기준
    //첫 정답
    answer = getAnswer(garo, sero, standard, xor_res, answer);
    
    //가로줄 기준을 바꾸기(flip한 형태로 - answer이 1부터 시작)
    standard = Flip(standard);
    int another_answer = getAnswer(garo, sero, standard, xor_res, 1);
    
    //비교 후 리턴
    if(answer > another_answer) return another_answer; 
    return answer;
}