테이블에 N개의 카드가 있고 각 카드의 양면에 양의 정수가 인쇄되어 있다고 가정합니다(아마도 다를 수 있음). 우리는 카드를 원하는 수만큼 뒤집어야 하고, 한 장의 카드를 선택한 후에야 합니다. 선택한 카드의 뒷면에 있는 숫자 X가 카드의 앞면에 없으면 숫자 X가 양호한 것으로 알려져 있습니다. 우리는 좋은 가장 작은 숫자를 찾아야합니까? 좋은 숫자가 없으면 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가 좋은 숫자입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- set s, n :=전면 크기, ret :=inf 정의
- 0 ~ n – 1 범위의 i에 대해
- fronts[i] =back[i]이면 s에 fronts[i]를 삽입합니다.
- 0 ~ n – 1 범위의 i에 대해
- if fronts[i]가 set then ret :=ret와 fronts[i]의 최소값
- 0 ~ n – 1 범위의 i에 대해
- backs[i]가 설정되지 않은 경우 ret :=ret 및 backs[i]의 최소값
- ret =inf이면 0을 반환하고, 그렇지 않으면 ret.
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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