문제 소개
1부터 n까지의 숫자가 무작위 순서로 섞여 있는 배열이 있다고 가정해 보겠습니다. 여기에 정수 K가 하나 더 주어집니다. N명의 사람들이 배드민턴 경기를 하기 위해 줄을 서서 대기 중이며, 게임은 다음 규칙에 따라 진행됩니다.
- 대기열 맨 앞의 두 명이 먼저 경기를 시작합니다.
- 진 사람은 대기열의 맨 뒤로 이동합니다.
- 이긴 사람은 대기열의 다음 사람과 계속해서 경기를 진행합니다.
- 누군가 K번 연속으로 승리하면 그 사람이 최종 우승자가 됩니다.
예제로 살펴보기
대기열이 [2, 1, 3, 4, 5]이고 K = 2일 때, 출력 결과는 5입니다. 진행 과정을 단계별로 확인해 보겠습니다.
- (2, 1) 경기 → 2 승리, 1은 맨 뒤로 → 대기열: [3, 4, 5, 1]
- (2, 3) 경기 → 3 승리, 2는 맨 뒤로 → 대기열: [4, 5, 1, 2]
- (3, 4) 경기 → 4 승리, 3은 맨 뒤로 → 대기열: [5, 1, 2, 3]
- (4, 5) 경기 → 5 승리, 4는 맨 뒤로 → 대기열: [1, 2, 3, 4]
- (5, 1) 경기 → 5 승리, 1은 맨 뒤로 → 대기열: [2, 3, 4, 1]
이 시점에서 5가 두 번 연속 승리했으므로 최종 우승자는 5입니다.
알고리즘
실제로 매 경기마다 대기열을 회전시키며 시뮬레이션할 필요는 없습니다. 핵심은 현재 최강자(best player)와 그 선수의 연속 승리 횟수(win count)를 추적하는 것입니다. 새로운 요소가 현재 최강자보다 작으면 최강자의 승리 횟수가 1씩 늘어나고, 더 큰 값이 등장하면 그 값이 새로운 최강자가 되며 승리 횟수가 초기화됩니다. 또한 K가 n-1보다 크거나 같다면 배열의 최댓값이 반드시 모든 상대를 이기게 되므로, 순회 없이 곧바로 n을 반환할 수 있습니다.
winner(arr, n, k)
Begin
if k >= n-1, then return n
best_player := 0
win_count := 0
for each element e in arr, do
if e > best_player, then
best_player := e
if e is 0th element, then
win_count := 1
end if
else
increase win_count by 1
end if
if win_count >= k, then
return best_player
done
return best_player
End
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 별도의 추가 메모리도 거의 필요하지 않아 매우 효율적입니다.
C++ 구현 예제
#include <iostream>
using namespace std;
int winner(int arr[], int n, int k) {
if (k >= n - 1) // K가 배열 크기 이상이면 최댓값 n 반환
return n;
int best_player = 0, win_count = 0; // 최강자와 승리 횟수 초기화
for (int i = 0; i < n; i++) { // 배열의 각 요소를 순회
if (arr[i] > best_player) { // 현재 최강자보다 크면 갱신
best_player = arr[i];
if (i) // 첫 번째 요소가 아니면 승리 횟수를 1로 설정
win_count = 1;
} else // 그렇지 않으면 승리 횟수 증가
win_count += 1;
if (win_count >= k) // 승리 횟수가 K 이상이면 결과 확정
return best_player;
}
return best_player; // 조건을 만족하지 못하면 최댓값이 우승
}
main() {
int arr[] = { 3, 1, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
cout << winner(arr, n, k);
}
실행 결과
3
배열 {3, 1, 2}에서 K = 2인 경우를 생각해 보면, 3이 먼저 1에게 승리한 뒤 이어서 2에게도 승리하여 두 번의 연속 승리를 달성하므로 최종 결과는 3이 됩니다.