테이블 위에 N장의 카드가 놓여 있다고 가정해 보겠습니다. 각 카드의 양면에는 양의 정수가 인쇄되어 있으며, 양면의 숫자는 서로 다를 수 있습니다. 우리는 원하는 만큼 카드를 뒤집은 후 한 장의 카드를 선택할 수 있습니다. 이때 선택한 카드 뒷면에 적힌 숫자 X가 어떤 카드의 앞면에도 존재하지 않는다면, 그 숫자 X를 '좋은(good) 숫자'라고 부릅니다. 목표는 이러한 좋은 숫자 중 가장 작은 값을 찾는 것이며, 만약 좋은 숫자가 하나도 존재하지 않는다면 0을 반환해야 합니다.
여기서 fronts[i]와 backs[i]는 각각 i번째 카드의 앞면과 뒷면에 적힌 숫자를 의미합니다. 카드를 뒤집으면 앞면과 뒷면의 값이 서로 교환됩니다. 즉, 기존 앞면의 값은 뒷면으로, 뒷면의 값은 앞면으로 바뀌게 됩니다.
예를 들어 fronts = [1,2,4,4,7], backs = [1,3,4,1,3]이 입력으로 주어진 경우 출력은 2가 됩니다. 두 번째 카드를 뒤집으면 앞면은 [1,3,4,4,7], 뒷면은 [1,2,4,1,3]이 됩니다. 이 상태에서 두 번째 카드를 선택하면 뒷면의 숫자는 2이고, 이 숫자는 어떤 카드의 앞면에도 존재하지 않으므로 2는 좋은 숫자입니다.
해결 접근 방법
이 문제의 핵심 아이디어는 다음과 같습니다. 만약 어떤 카드의 앞면과 뒷면 숫자가 동일하다면(fronts[i] == backs[i]), 그 숫자는 카드를 아무리 뒤집어도 반드시 해당 카드의 앞면에 존재하게 되므로 절대로 좋은 숫자가 될 수 없습니다. 따라서 이런 숫자들을 먼저 집합(set)에 모아두고, 나머지 숫자들 중에서 최솟값을 찾으면 됩니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- 집합 s를 정의하고, n := fronts의 크기, ret := 무한대(INT_MAX)로 초기화합니다.
- i를 0부터 n-1까지 반복하며, fronts[i] == backs[i]라면 fronts[i]를 집합 s에 추가합니다. 이 숫자들은 좋은 숫자가 될 수 없습니다.
- i를 0부터 n-1까지 반복하며, fronts[i]가 집합 s에 존재하지 않는다면 ret을 ret과 fronts[i] 중 더 작은 값으로 갱신합니다.
- i를 0부터 n-1까지 반복하며, backs[i]가 집합 s에 존재하지 않는다면 ret을 ret과 backs[i] 중 더 작은 값으로 갱신합니다.
- ret이 여전히 무한대라면 0을 반환하고, 그렇지 않으면 ret을 반환합니다.
C++ 코드 구현
아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int flipgame(vector<int>& fronts, vector<int>& backs) {
set <int> s;
int n = fronts.size();
int ret = INT_MAX;
for(int i = 0; i < n; i++){
if(fronts[i] == backs[i])s.insert(fronts[i]);
}
for(int i = 0; i <n; i++ ){
if(s.count(fronts[i]) == 0) ret = min(ret, fronts[i]);
}
for(int i = 0; i <n; i++ ){
if(s.count(backs[i]) == 0) ret = min(ret, backs[i]);
}
return ret == INT_MAX? 0 : ret;
}
};
main(){
vector<int> v1 = {1,2,4,4,7};
vector<int> v2 = {1,3,4,1,3};
Solution ob;
cout << (ob.flipgame(v1, v2));
}입력
[1,2,4,4,7] [1,3,4,1,3]
출력
2
이 알고리즘의 시간 복잡도는 O(n)이며, 공간 복잡도 역시 O(n)입니다. 카드 배열을 세 번 순회하면서 양면이 같은 카드의 숫자를 제외한 나머지 값들의 최솟값을 효율적으로 구할 수 있습니다.