Amal과 Bimal이 숫자로 이루어진 배열 A 하나를 두고 게임을 한다고 가정해 보겠습니다. 게임 규칙은 다음과 같습니다.
- 항상 Bimal이 먼저 시작합니다.
- 각 턴마다 플레이어는 배열에서 최댓값 요소 하나를 삭제하며, 삭제된 요소의 오른쪽에 있는 모든 요소 역시 함께 삭제됩니다.
- 두 플레이어는 번갈아 가며 게임을 진행합니다.
- 남아 있는 모든 요소를 제거한 플레이어가 승리합니다.
예를 들어 입력이 nums = [5, 2, 6, 3, 4]라면 결과는 Amal입니다. Bimal이 첫 턴에 [6, 3, 4]를 제거하면 배열은 [5, 2]로 줄어들고, 이어서 Amal이 나머지 요소를 모두 제거하여 승자가 되기 때문입니다.
접근 방법
이 문제의 핵심은 배열을 왼쪽에서 오른쪽으로 훑으며 '그때까지의 최댓값을 경신하는 요소', 즉 접두사 최댓값(prefix maximum)이 몇 번 등장하는지 세는 것입니다. 매 턴마다 현재 최댓값이 제거되고 그 오른쪽 요소들도 함께 사라지므로, 다음 턴의 최댓값은 반드시 앞선 모든 요소보다 큰 값이 됩니다. 따라서 전체 게임의 총 턴 수는 접두사 최댓값의 개수와 정확히 일치합니다.
- maximum을 -1로, count를 0으로 초기화합니다.
- nums의 각 요소 a에 대해 다음을 반복합니다.
- a > maximum이면 count를 1 증가시키고 maximum을 a로 갱신합니다.
- count가 짝수이면 "Amal"을 반환하고, 그렇지 않으면 "Bimal"을 반환합니다.
즉, 총 턴 수가 홀수이면 마지막 수를 두는 Bimal이, 짝수이면 Amal이 승리합니다.
예제 코드
def solve(nums):
maximum = -1
count = 0
for a in nums:
if a > maximum:
count += 1
maximum = a
if count % 2 == 0:
return "Amal"
return "Bimal"
nums = [5, 2, 6, 3, 4]
print(solve(nums))입력
[5, 2, 6, 3, 4]
출력
Amal
복잡도 분석
배열을 한 번만 순회하면 되므로 시간 복잡도는 O(n)이며, 추가 변수 몇 개만 사용하므로 공간 복잡도는 O(1)입니다. 덕분에 배열의 길이가 매우 크더라도 승자를 빠르게 판별할 수 있습니다.