[1일 1알고] 2차원 동전 뒤집기

https://school.programmers.co.kr/learn/courses/30/lessons/131703

프로그래머스

구현 문제입니다.

 

어떻게 뒤집어야하는지는 하나의 열 혹은 행에 대한 상태를 결정하면 나머지는 뒤따라옵니다.

 

하나의 열을 결정하면 target에 맞추기 위해 행의 flip상태가 모두 결정나고 반대로도 마찬가지입니다.

 

따라서 첫번째 열을 뒤집은 경우, 그대로 둔 경우로 나눠 이후 구현해나가면 됩니다.

 

문제는 XOR를 적극적으로 사용할 것을 권장하는 것 처럼 보입니다.

flip을 하기 위한 가장 간단한 방법은 0과 1로 이루어진 기존 값에 XOR1을 하는 것이기 때문입니다.

---

#include <string>
#include <vector>

using namespace std;


int solution(vector<vector<int>> beginning, vector<vector<int>> target) {
    int answer = -1;

    int N = beginning.size();
    int M = beginning[0].size();
    vector<int> columns(M, 0); // 0 = 그대로, 1 = flip

    int colcnt = 0;
    // 첫 행은 그대로라고 가정
    for (int j = 0; j < M; ++j)
    {
        if (beginning[0][j] != target[0][j])
        {
            columns[j] = 1;
            ++colcnt;
        }
    }

    int temp = 0;
    for (int i = 1; i < N; ++i)
    {
        bool flag = true;
        for (int j = 0; j < M; ++j)
        {
            int cur = beginning[i][j] ^ columns[j];

            if (cur != target[i][j])
            {
                flag = false;
                break;
            }
        }
        if (flag)
            continue;
        flag = true;
        for (int j = 0; j < M; ++j)
        {
            int cur = beginning[i][j] ^ 1 ^ columns[j];

            if (cur != target[i][j])
            {
                flag = false;
                break;
            }
        }

        if (flag)
        {
            ++temp;
        }
        else
        {
            temp = -1;
            break;
        }
    }

    if (temp != -1)
    {
        answer = temp + colcnt;
    }

    for (int i = 0; i < M; ++i)
    {
        columns[i] ^= 1;
    }
    colcnt = M - colcnt;

    temp = 0;
    // 첫 행이 뒤집힌 경우
    for (int i = 1; i < N; ++i)
    {
        bool flag = true;
        for (int j = 0; j < M; ++j)
        {
            int cur = beginning[i][j] ^ columns[j];

            if (cur != target[i][j])
            {
                flag = false;
                break;
            }
        }
        if (flag)
            continue;
        flag = true;
        for (int j = 0; j < M; ++j)
        {
            int cur = beginning[i][j] ^ 1 ^ columns[j];

            if (cur != target[i][j])
            {
                flag = false;
                break;
            }
        }

        if (flag)
        {
            ++temp;
        }
        else
        {
            temp = -1;
            break;
        }
    }
    if (temp != -1)
    {
        int cur = temp + colcnt + 1;

        if (answer == -1)
            answer = cur;
        else
            answer = min(answer, cur);
    }

    return answer;
}

결론적인 코드입니다.

반복되는 부분이 있지만 모듈화를 한다면 더 간단하게 풀 수 있겠네요

---

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int check(const vector<vector<int>>& beginning,
          const vector<vector<int>>& target,
          bool flipFirstRow)
{
    int N = beginning.size();
    int M = beginning[0].size();

    vector<int> colFlip(M, 0);
    int count = 0;

    // 첫 행을 뒤집는 경우라면 count 1 증가
    if (flipFirstRow)
        ++count;

    // 첫 행을 기준으로 각 열을 뒤집을지 결정
    for (int j = 0; j < M; ++j)
    {
        int cur = beginning[0][j];

        if (flipFirstRow)
            cur ^= 1;

        if (cur != target[0][j])
        {
            colFlip[j] = 1;
            ++count;
        }
    }

    // 나머지 행 검사
    for (int i = 1; i < N; ++i)
    {
        bool same = true;
        bool reversed = true;

        for (int j = 0; j < M; ++j)
        {
            int cur = beginning[i][j] ^ colFlip[j];

            // 행을 안 뒤집었을 때 맞는가?
            if (cur != target[i][j])
                same = false;

            // 행을 뒤집었을 때 맞는가?
            if ((cur ^ 1) != target[i][j])
                reversed = false;
        }

        if (same)
        {
            continue;
        }
        else if (reversed)
        {
            ++count;
        }
        else
        {
            return -1;
        }
    }

    return count;
}

int solution(vector<vector<int>> beginning, vector<vector<int>> target)
{
    int case1 = check(beginning, target, false); // 첫 행 안 뒤집음
    int case2 = check(beginning, target, true);  // 첫 행 뒤집음

    if (case1 == -1 && case2 == -1)
        return -1;

    if (case1 == -1)
        return case2;

    if (case2 == -1)
        return case1;

    return min(case1, case2);
}

이는 AI를 통해 만든 코드입니다. 전체적인 가닥은 비슷하지만 check라는 함수를 만들어 분리해주었네요