두 친구 Amal과 Bimal이 nums라고 하는 정렬된 숫자 목록으로 게임을 하고 있다고 가정합니다. 이 게임에서 한 턴에 Amal은 세 개의 숫자를 선택합니다. Bimal은 그들 중 하나를 제거하고 Amal은 그 중 하나를 제거합니다. 목록은 홀수 개수의 요소로 시작합니다. 여기서 Amla는 목록에 반복되는 요소가 포함되지 않도록 하는 데 필요한 회전 수를 최소화하기를 원하고 Bimal은 회전 수를 최대화하기를 원합니다. Amal과 Bimal이 최적으로 행동한다면 이 게임에 필요한 턴 수를 찾아야 합니다.
따라서 입력이 nums =[1, 1, 2, 3, 3, 3, 4]와 같으면 출력은 2가 됩니다. Amal이 [1, 1, 3]을 선택하면 Bimal이 3을 제거하여 최대화하기 때문입니다. 턴, 배열은 [1, 1, 2, 3, 3, 4]이고 Amal은 1을 제거하므로 배열은 [1,2,3,3,4]이고 다음 차례에서 Amal은 [3,3, 4], Bimal은 4를 제거하여 턴을 최대화합니다. 따라서 Amal은 3을 제거할 수 있고 배열은 [1,2,3]이 되며 중복 요소가 없습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
반복 :=0
범위 1에서 숫자 크기까지의 i에 대해
nums[i]가 nums[i-1]과 같으면
반복 :=반복 + 1
(반복 + 1) / 2의 반환 몫
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
class Solution: def solve(self, nums): repeats = 0 for i in range(1, len(nums)): if nums[i] == nums[i-1]: repeats += 1 return (repeats + 1) // 2 ob = Solution() nums = [1, 1, 2, 3, 3, 3, 4] print(ob.solve(nums))
입력
[1, 1, 2, 3, 3, 3, 4]
출력
2