문제 개요
서로 다른 고유한 원소로 이루어진 배열 arr와 정수 k가 주어져 있다고 가정해 보겠습니다. 이제 다음 규칙을 따르는 간단한 게임을 생각할 수 있습니다.
- 매 라운드마다 배열의 첫 두 원소인 arr[0]과 arr[1]을 비교합니다.
- 더 큰 값이 승리하여 0번째 자리에 그대로 남고, 작은 값은 배열의 맨 끝으로 이동합니다.
- 어떤 값이 k번 연속으로 승리하면 게임이 종료되며, 그 값이 최종 승자가 됩니다.
예를 들어 입력이 arr = [1,5,6,3,4,2], k = 3이라면 출력은 6이 됩니다. 라운드별 진행 과정은 다음과 같습니다.
라운드 1: arr = [1,5,6,3,4,2] → 승자는 5, 5의 연속 승리 횟수 1
라운드 2: arr = [5,6,3,4,2,1] → 승자는 6, 6의 연속 승리 횟수 1
라운드 3: arr = [6,3,4,2,1,5] → 승자는 6, 6의 연속 승리 횟수 2
라운드 4: arr = [6,4,2,1,5,3] → 승자는 6, 6의 연속 승리 횟수 3
결국 6이 세 번(k = 3) 연속 승리했으므로 최종 승자는 6입니다.
알고리즘 접근 방법
이 문제는 배열을 실제로 재배열하지 않고도 현재 리더(0번째 자리의 값)만 추적하면 효율적으로 해결할 수 있습니다. 단계별 풀이는 다음과 같습니다.
- l := 배열 arr의 크기
- prev := arr[0] (현재 리더)
- count := 0 (연속 승리 횟수)
- i를 1부터 l-1까지 반복합니다.
- prev > arr[i]이면 count를 1 증가시킵니다. (현재 리더가 다시 승리)
- 그렇지 않으면 prev := arr[i], count := 1로 갱신합니다. (더 큰 새 값이 리더가 됨)
- count == k이면 prev를 반환하고 종료합니다.
- 반복이 모두 끝나면 prev를 반환합니다.
Python 구현 예제
다음 코드를 통해 실제 동작을 확인해 보겠습니다.
def solve(arr, k):
l = len(arr)
prev = arr[0]
count = 0
for i in range(1, l):
if prev > arr[i]:
count += 1
else:
prev = arr[i]
count = 1
if count == k:
return prev
return prev
arr = [1,5,6,3,4,2]
k = 3
print(solve(arr, k))
입력
[1,5,6,3,4,2], 3
출력
6
복잡도 및 핵심 포인트
이 알고리즘은 배열의 각 원소를 한 번씩만 확인하므로 시간 복잡도는 O(n)이며, 별도의 저장 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다.
흥미로운 점은, 한 번의 순회가 끝났을 때 아직 k번 연속 승리에 도달하지 못한 경우에도 prev를 그대로 반환해도 정답이라는 것입니다. 순회가 끝난 시점의 prev는 배열의 최댓값이며, 최댓값은 이후 어떤 원소와 비교해도 지지 않기 때문에 결국 k번 연속 승리하게 되기 때문입니다. 덕분에 무한히 긴 게임 시뮬레이션 없이도 선형 시간 안에 승자를 확정할 수 있습니다.