[프로그래머스][C++] 2차원 동전 뒤집기
2차원 동전 뒤집기
문제 링크
분석
m x n크기의 격자에 앞면(0), 뒷면(1)으로 뒤집혀 있는 동전들이 놓여 있습니다.
놓여진 동전들을 목표 상태로 만들어야 합니다.
목표 상태로 만들기 위해서 동전을 뒤집을 때 같은 줄에 있는 모든 동전을 뒤집어야합니다.
이때, 같은 줄은 한 행이나 한 열을 뒤집어야합니다.
초기 상태에서 최소 몇 번의 동전을 뒤집어야 목표 상태를 만들 수 있는지 뒤집기 횟수의 최솟값을 반환해야합니다.
만약 만들 수 없는 경우 -1을 반환합니다.
beginning은 2차원 배열로 초기 상태를 나타냅니다.
target은 2차원 배열로 목표 상태를 나타냅니다.
풀이
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> beginning, vector<vector<int>> target) {
int answer = INT_MAX;
int m = beginning.size();
int n = beginning[0].size();
// 모든 행 뒤집기 조합을 탐색
for (int bit = 0; bit < (1 << m); ++bit)
{
// 현재 조합에 따른 시뮬레이션용 복사
vector<vector<int>> temp = beginning;
// 현재 비트 조합에 따라 각 행을 뒤집는다.
for (int i = 0; i < m; ++i)
{
// i번째 행을 뒤집는 경우
if (bit & (1 << i))
{
for (int j = 0; j < n; ++j)
{
// 0과 1을 반전
temp[i][j] ^= 1;
}
}
}
// 열 뒤집기 여부를 저장할 배열
vector<bool> colFlip(n, false);
// 열은 첫 번째 행 기준으로 판단
// temp[0][j]와 target[0][j]가 다르면 열 j를 뒤집어야한다.
for (int j = 0; j < n; ++j)
{
if (temp[0][j] != target[0][j])
{
colFlip[j] = true;
for (int i = 0; i < m; ++i)
{
temp[i][j] ^= 1;
}
}
}
// temp가 target과 같은지 확인한다.
bool ok = true;
for (int i = 0; i < m && ok; ++i)
{
for (int j = 0; j < n && ok; ++j)
{
if (temp[i][j] != target[i][j])
{
// 하나라도 다른 경우 실패
ok = false;
}
}
}
// 같은 경우 연산 횟수 계산
if (ok)
{
// 비트 켠 횟수
int rowCount = __builtin_popcount(bit);
// 열 뒤집은 횟수
int colCount = 0;
for (bool e : colFlip)
{
colCount += e;
}
// 최소 연산 횟수 갱신
answer = min(answer, rowCount + colCount);
}
}
return (answer == INT_MAX) ? -1 : answer;
}
for (int bit = 0; bit < (1 << m); ++bit) 에서 bit < (1 << m)는 0부터 $2^m - 1$까지 반복합니다.
각 비트 위치는 해당 행을 뒤집을지 여부를 나타냅니다.
즉, m = 3일 때, bit가 0일 경우 이진수로 000을 의미하며 아무 행도 뒤집지 않습니다.
bit가 1일 경우 이진수로 001을 의미하며 2번 행만 뒤집습니다.
bit가 2일 경우 이진수로 010을 의미하며 1번 행만 뒤집습니다.
bit가 3일 경우 이진수로 011을 의미하며 1, 2 번 행을 뒤집습니다.
bit & (1 << i)는 i번째 비트가 1인지 확인하는 코드입니다.
i번째 행을 뒤집는 조합인지 판단하는 조건이 됩니다.
__builtin_popcount는 정수의 이진수 표현에서 1의 개수를 세는 함수입니다.
현재 로직에서 1은 몇 개의 행을 뒤집었는지를 의미하므로 뒤집은 횟수를 구할 수 있습니다.
성능 요약
시간 복잡도는 $O(2^m \times m \times n)$입니다.
- 행 뒤집기 조합을 탐색하는 반복문 $O(2^m)$
- 행 뒤집기 반복문 $O(m \times n)$
- 열 뒤집기 반복문 $O(n \times m)$
temp와target을 비교하는 반복문 $O(m \times n)$- $O(2^m) \times (O(m \times n) + O(n \times m) + O(m \times n))$
공간 복잡도는 $O(m \times n)$입니다.
- 현재 조합에 따른 시뮬레이션용 복사 벡터
vector<vector<int>> temp$O(m \times n)$ - 열 뒤집기 여부를 저장하는 배열
vector<bool> colFlip$O(n)$ - $O(m \times n) + O(n)$
테스트 성능
테스트 1 〉 통과 (0.55ms, 4MB)
테스트 2 〉 통과 (0.03ms, 3.71MB)
테스트 3 〉 통과 (0.06ms, 4.11MB)
테스트 4 〉 통과 (0.13ms, 4.14MB)
테스트 5 〉 통과 (0.17ms, 4.14MB)
테스트 6 〉 통과 (0.02ms, 3.61MB)
테스트 7 〉 통과 (0.03ms, 4.18MB)
테스트 8 〉 통과 (0.03ms, 4.14MB)
테스트 9 〉 통과 (0.02ms, 4.18MB)
테스트 10 〉 통과 (0.12ms, 3.62MB)
테스트 11 〉 통과 (0.56ms, 3.66MB)
테스트 12 〉 통과 (0.58ms, 4.18MB)
테스트 13 〉 통과 (0.56ms, 3.59MB)
테스트 14 〉 통과 (0.56ms, 4.16MB)
테스트 15 〉 통과 (0.01ms, 4.19MB)
테스트 16 〉 통과 (0.01ms, 4.16MB)
테스트 17 〉 통과 (0.01ms, 4.18MB)
테스트 18 〉 통과 (0.52ms, 4.2MB)
테스트 19 〉 통과 (0.01ms, 4.18MB)
테스트 20 〉 통과 (0.01ms, 4.18MB)
테스트 21 〉 통과 (0.01ms, 4.18MB)
댓글남기기