소문자로만 구성된 문자열 S가 주어지고, 두 명의 플레이어가 이 문자열을 놓고 게임을 진행한다고 가정해 보겠습니다. 게임 규칙은 다음과 같습니다.
자신의 차례에 문자열의 문자들을 재배열하여 회문(palindrome)을 만들 수 있다면 해당 플레이어가 즉시 승리합니다.
반대로 문자열에서 문자를 하나 제거해야만 하는 상황이라면 그 차례에는 승리할 수 없습니다.
두 플레이어 모두 항상 최적의 전략으로 게임을 진행하며, 플레이어 1이 선공입니다. 이때 최종 승자가 누구인지 구해야 합니다.
예를 들어 입력이 "pqpppq"라면 출력은 플레이어 1입니다. 플레이어 1이 첫 번째 차례에서 문자들을 재배열해 "ppqqpp"라는 회문을 만들 수 있어 곧바로 승리하기 때문입니다.
핵심 아이디어: 문자 빈도의 홀짝성
회문은 각 문자의 등장 횟수와 깊은 관련이 있습니다. 어떤 문자열을 재배열해 회문을 만들 수 있으려면, 홀수 번 등장하는 문자가 최대 1개여야 합니다. 이 성질을 이용하면 다음과 같이 승자를 판별할 수 있습니다.
홀수 빈도를 가진 문자가 전혀 없으면(count = 0), 첫 차례에 바로 회문을 만들 수 있으므로 플레이어 1이 승리합니다.
홀수 빈도를 가진 문자의 개수(count)가 홀수이면, 문자가 제거될 때마다 홀짝성이 뒤집히므로 결국 플레이어 1의 차례에 회문 조건이 충족됩니다.
홀수 빈도를 가진 문자의 개수가 양수인 짝수이면, 같은 논리에 따라 플레이어 2가 승리합니다.
해결 단계
위 아이디어를 바탕으로 다음 단계를 따릅니다.
l := 문자열의 길이
freq := 크기가 26이고 0으로 채워진 리스트 생성 (각 알파벳의 등장 횟수 저장)
i를 0부터 l-1까지 반복하며 sequence[i]에 해당하는 freq 값을 1씩 증가
count := 0으로 초기화
i를 0부터 25까지 반복하며 freq[i]가 홀수일 때마다 count를 1 증가
count가 0이거나 홀수이면 1을 반환하고, 그렇지 않으면 2를 반환
구현 예제
다음 파이썬 코드를 통해 더 자세히 이해해 보겠습니다.
def who_is_the_winner(sequence):
l = len(sequence)
freq = [0 for i in range(26)]
for i in range(0, l, 1):
freq[ord(sequence[i]) - ord('a')] += 1
count = 0
for i in range(26):
if (freq[i] % 2 != 0):
count += 1
if (count == 0 or count & 1 == 1):
return 1
else:
return 2
sequence = "pqpppq"
print("Player:", who_is_the_winner(sequence))입력
"pqpppq"
출력
Player: 1
실행 결과 플레이어 1이 이 게임의 승자임을 확인할 수 있습니다. 이 알고리즘은 문자열을 한 번만 순회하면 되므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.