[C] LeetCode 1823. Find the Winner of the Circular Game

문제

번역

게임에 참여하는 친구가 n명 있다. 이 친구들은 원형으로 앉아서 1번부터 n번까지 시계방향 순서로 번호를 부여받는다.

좀 더 정확하게, i번째에서 시계 방향으로 이동하면 i+1 번째 친구에게 가게 되고, n번째 친구는 1번 친구에게 다시 가게 된다.

 

게임의 룰은 아래와 같다.

1. 1번 친구부터 시작한다.

2. 시작한 친구를 포함해서, 시계방향으로 다음 k명의 친구를 센다 원을 따라서 계속 세므로 한바퀴를 넘어가거나 두번 이상 셀 수 도 있다.

3. 마지막으로 센 친구가 원에서 빠지고 게임에서 진다.

4. 여전히 1명보다 많은 친구가 원에 있으면 2번부터 다시 수행한다.

5. 그렇지 않으면 마지막으로 남은 친구가 게임에서 이긴다.

 

n명의 친구가 주어지고, k 정수가 주어졌을 때 게임의 승자를 구해라.

접근 방법 및 소스코드

처음에는 가장 단순하게 n개의 크기만큼 배열을 만들고, 해당 배열에서 flag 형식으로 관리하면서 풀려고 했다.

하지만 문제의 맨 아래에 해당 문제를 O(n)의 시간복잡도와 O(1)의 공간복잡도로 문제를 풀라고 했기에 해당 방법은 포기했다.

 

일단, 사람이 1명만 있으면 해당 사람이 곧 마지막 사람이므로 승자가 된다. 이 경우 바로 해당 값을 반환해주어야 한다.

 

이제 사람을 하나 제거한다고 생각하자.

그러면 탈락하는 사람은 k mod n 번째 자리에 위치한 사람이 될 것이다.

이 사람이 빠지고 나면 게임은 결국 사람 수가 n-1로 줄어들은 똑같은 문제가 된다. 그래서 재귀로 접근할 수 있다.

 

그래서 남은 문제의 승자의 위치는 재귀적으로 n-1, k로 구할 수 있다. 문제는 이 경우는 새롭게 번호를 다시 매긴 경우이다.

새롭게 시작한 위치는 원래 n명 기준으로, 기존 시작점에서 k칸 이동한 위치이다.

 

그렇기에 해당 값에다 k를 더해서 탈락한 사람의 위치를 구해야 한다.

 

해서 아래처럼 코드를 쓸 수 있다.

int recur(int n, int k) {
    if(n==1) return 0;
    return (recur(n-1, k) + k) % n;
}
int findTheWinner(int n, int k) {
    return recur(n,k)+1;
}