문제 개요
단어 목록이 주어져 있다고 가정해 봅시다. 두 명의 플레이어가 참여하는 '고스트(Ghost) 게임'을 생각해 보겠습니다. 이 게임의 규칙은 다음과 같습니다.
- 두 플레이어는 번갈아 가며 문자열 끝에 글자를 하나씩 추가합니다.
- 만들어지는 문자열은 항상 단어 목록에 있는 어떤 단어의 유효한 접두사(prefix)여야 합니다.
- 목록 속 단어 하나를 완성해서 말하게 된 플레이어가 패배합니다.
양쪽 플레이어 모두 최적의 전략으로 플레이한다고 할 때, 첫 번째 플레이어가 승리할 수 있는지 확인해야 합니다.
예를 들어 입력이 words = ["manage", "manager", "min"]이라면 출력은 True입니다. 실제 진행 과정은 다음과 같습니다.
- m — 플레이어 1
- ma — 플레이어 2
- man — 플레이어 1
- mana — 플레이어 2
- manag — 플레이어 1
- manage — 플레이어 2, 패배
결국 플레이어 1이 승리하게 됩니다.
풀이 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 맵(map) mp를 하나 선언합니다.
- words의 각 단어 it에 대해 다음을 수행합니다.
- ch := it[0] (단어의 첫 글자)
- it를 mp[ch] 집합에 삽입합니다.
- mn := 무한대(inf)로 초기화합니다.
- mp의 각 키-값 쌍 it에 대해 다음을 수행합니다.
- str := 해당 값(집합에서 사전순으로 가장 앞선 단어)
- size := str의 길이
- size를 2로 나눈 나머지가 0이라면(길이가 짝수라면) 1을 반환합니다.
- 모든 그룹을 확인한 후에도 짝수 길이 단어가 없다면 0을 반환합니다.
동작 원리
핵심은 단어 길이의 홀짝성입니다. 플레이어 1이 1번째, 3번째, 5번째처럼 홀수 번째 글자를 붙이고, 플레이어 2가 짝수 번째 글자를 붙입니다. 단어를 완성하는 순간 그 플레이어가 지기 때문에, 길이가 짝수인 단어는 마지막 글자를 플레이어 2가 붙이게 되어 플레이어 2가 패배합니다. 따라서 특정 시작 문자로 출발해 짝수 길이의 단어로 게임을 끝낼 수 있다면 첫 번째 플레이어의 승리입니다.
예제 코드 (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
출력이 1(True)이므로, 양쪽 모두 최적으로 플레이할 때 첫 번째 플레이어가 승리할 수 있다는 것을 의미합니다.