단어 목록이 있다고 가정합니다. 이제 두 명의 플레이어가 참여할 수 있는 유령 게임을 생각해 보십시오. 여기서 플레이어는 문자열에 문자를 번갈아 추가합니다. 그리고 만들고 있는 문자열은 목록에 있는 단어의 유효한 접두어여야 하며 목록에 있는 단어를 철자하는 플레이어는 패배합니다. 두 플레이어가 모두 최적의 플레이를 하고 있다면 첫 번째 플레이어가 이길 수 있는지 여부를 확인해야 합니다.
따라서 입력이 단어 =["manage", "manager", "min"]과 같으면 출력은 True가 됩니다.
- m [플레이어 1]
- 엄마 [플레이어 2]
- 남자 [플레이어 1]
- 마나 [플레이어 2]
- [플레이어 1] 관리
- [플레이어 2] 패배 관리
따라서 플레이어 1이 이깁니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 하나의 지도 MP 정의
- 각 단어에 대해 다음을 수행합니다.
- ch :=그것[0]
- mp[ch]에 삽입
- mn :=정보
- 각 키-값 쌍에 대해 mp 단위로 수행합니다.
- str :=값
- 크기 :=str의 크기
- 크기 mod 2가 0과 같으면 -
- 1 반환
- 0을 반환
예시(C++)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
bool solve(vector<string> &words) {
map<char, set<string>> mp;
for (auto &it : words) {
char ch = it[0];
mp[ch].insert(it);
}
int mn = INT_MAX;
for (auto &it : mp) {
string str = *(it.second.begin());
int size = str.size();
if (size % 2 == 0)
return 1;
}
return 0;
}
int main(){
vector<string> v = {"manage", "manager", "min"};
cout << solve(v);
} 입력
{"manage", "manager", "min"} 출력
1