숫자로 이루어진 리스트 candies가 주어지고, 두 친구가 캔디 제거 게임을 한다고 가정해 보겠습니다. 각 라운드마다 플레이어는 값이 같은 인접한 두 개의 캔디를 제거할 수 있습니다. 그리고 더 이상 제거할 캔디가 없는 플레이어가 지며, player1이 먼저 시작합니다. 우리가 확인해야 할 것은 player1이 최종적으로 승리하는지 여부입니다.
예를 들어 입력이 nums = [2, 2, 5]라면 결과는 True가 됩니다. player1이 먼저 연속된 두 개의 2를 제거하면 상대방에게는 캔디 5 하나만 남기 때문에, 상대방은 어떤 캔디도 제거할 수 없어서 바로 지게 됩니다.
해결 접근 방식: 스택 활용
이 문제는 스택(stack) 자료구조를 사용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 빈 스택을 준비하고 턴 카운터(turns)를 0으로 초기화합니다.
- 리스트의 각 숫자를 순회하면서, 스택이 비어 있지 않고 스택의 맨 위 숫자가 현재 숫자와 같다면 스택에서 pop하고 turns를 1 증가시킵니다. 이는 실제 게임에서 한 번의 캔디 제거(한 턴)에 해당합니다.
- 그렇지 않으면 현재 숫자를 스택에 push합니다.
- 모든 숫자를 처리한 후, turns가 홀수이면 True(첫 번째 플레이어 승리), 짝수이면 False를 반환합니다.
게임 이론적인 관점에서 설명하면, 제거 가능한 총 횟수는 리스트가 고정되어 있는 한 일정합니다. 양쪽 플레이어 모두 최선을 다해 제거한다고 할 때, 총 턴 수가 홀수라면 반드시 첫 번째 플레이어가 마지막 제거를 수행하게 되므로 승리합니다.
예제 코드
class Solution:
def solve(self, nums):
stack = []
turns = 0
for num in nums:
if stack and stack[-1] == num:
stack.pop()
turns += 1
else:
stack.append(num)
return bool(turns & 1)
ob = Solution()
nums = [2, 2, 5]
print(ob.solve(nums))
입력
[2, 2, 5]
출력
True
복잡도 분석
이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 스택에 최악의 경우 모든 원소가 저장될 수 있으므로 공간 복잡도 역시 O(n)입니다. 비트 연산 turns & 1을 통해 홀수 여부를 빠르게 판별하는 점도 눈여겨볼 만합니다.