소문자가 포함된 문자열 S가 있다고 가정하고 이제 두 명의 플레이어가 게임을 하고 있습니다. 규칙은 다음과 같습니다 -
-
플레이어가 이동 시 문자열의 문자를 섞어 회문 문자열을 얻을 수 있는 경우 플레이어가 게임에서 승리합니다.
-
플레이어는 문자열에서 문자를 제거해야 할 때 승리할 수 없습니다.
우리는 두 플레이어 모두 게임을 최적으로 플레이하고 플레이어 1이 게임을 시작한다는 점을 명심해야 합니다. 게임의 승자를 찾아야 합니다.
따라서 입력이 "pqpppq"와 같으면 첫 번째 단계에서 플레이어-1이 캐릭터를 정렬하여 "ppqqpp"를 얻고 게임에서 승리하므로 출력은 Player1이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
l :=시퀀스의 크기
-
freq :=크기가 26이고 0으로 채워진 목록을 만듭니다.
-
범위 0에서 l의 i에 대해 1씩 증가, 수행
-
시퀀스[i]의 주파수를 1 증가
-
개수 :=0
-
0에서 25 사이의 i에 대해 수행
-
freq[i] mod 2가 0이 아니면
-
개수 :=개수 + 1
-
-
-
개수가 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