문제 소개
정렬된 숫자 리스트 nums를 가지고 두 친구 아말(Amal)과 비말(Bimal)이 게임을 한다고 가정해 봅시다. 게임 규칙은 다음과 같습니다.
- 각 턴에서 아말은 리스트에서 임의의 숫자 세 개를 선택합니다.
- 비말이 선택된 숫자 중 하나를 먼저 제거하고, 그다음 아말이 하나를 더 제거합니다.
- 리스트는 처음에 홀수 개의 원소로 시작하며, 매 턴 정확히 두 개의 원소가 사라집니다.
아말은 리스트에 중복된 원소가 남지 않도록 만드는 데 필요한 턴 수를 최소화하려 하고, 비말은 반대로 턴 수를 최대화하려 합니다. 두 사람이 모두 최선의 전략으로 플레이할 때, 이 게임을 끝내기 위해 총 몇 번의 턴이 필요한지 구하는 것이 목표입니다.
입력 예시
예를 들어 입력이 다음과 같다고 해보겠습니다.
nums = [1, 1, 2, 3, 3, 3, 4]
이 경우 출력은 2입니다. 진행 과정은 다음과 같습니다.
- 아말이
[1, 1, 3]을 선택하면, 비말은 턴 수를 늘리기 위해 3을 제거합니다. 배열은[1, 1, 2, 3, 3, 4]가 되고, 이어서 아말이 1을 제거해[1, 2, 3, 3, 4]가 됩니다. - 다음 턴에서 아말이
[3, 3, 4]를 선택하면, 비말은 4를 제거하고, 아말이 3을 제거합니다. 최종 배열은[1, 2, 3]으로 더 이상 중복 원소가 없습니다.
해결 접근 방법
핵심 아이디어는 의외로 단순합니다. 리스트가 이미 정렬되어 있으므로, 인접한 두 원소가 같은 지점의 개수(중복 쌍의 수)만 세면 됩니다. 한 턴에 최대 두 개의 중복을 없앨 수 있기 때문에, 필요한 턴 수는 중복 쌍의 수를 2로 나눈 값을 올림한 것, 즉 (repeats + 1) // 2가 됩니다.
단계별로 정리하면 다음과 같습니다.
repeats를 0으로 초기화합니다.- 인덱스 1부터 리스트 끝까지 순회하면서,
nums[i]가nums[i-1]과 같으면repeats를 1 증가시킵니다. (repeats + 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
복잡도 분석
- 시간 복잡도: O(n) — 리스트를 한 번만 순회하면 됩니다.
- 공간 복잡도: O(1) — 추가 메모리 없이 카운터 변수 하나만 사용합니다.