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

https://leetcode.com/problems/find-the-winner-of-the-circular-game/description/

leetcode - Find the Winner of the Circular Game

문제 유형 : 배열

문제 난이도 : Medium

 

문제

There are n friends that are playing a game. The friends are sitting in a circle and are numbered from 1 to n in clockwise order. More formally, moving clockwise from the ith friend brings you to the (i+1)th friend for 1 <= i < n, and moving clockwise from the nth friend brings you to the 1st friend.

The rules of the game are as follows:

1. Start at the 1st friend.
2. Count the next k friends in the clockwise direction including the friend you started at. The counting wraps around the circle and may count some friends more than once.
3. The last friend you counted leaves the circle and loses the game.
4. If there is still more than one friend in the circle, go back to step 2 starting from the friend immediately clockwise of the friend who just lost and repeat.
5. Else, the last friend in the circle wins the game.

Given the number of friends, n, and an integer k, return the winner of the game.

 

n명의 친구가 게임을 하고 있다.

원형으로 앉아서 시계방향으로 1부터 n까지 번호를 가진다.

게임의 규칙은 다음과 같다:

 

1. 첫 번째 친구부터 시작한다.
2. 다음 k번째 친구를 찾아서 탈락시킨다. 시작 친구를 포함한다.
3. 그 다음 친구부터 다시 시작한다.
4. 만약 2명 이상이면, 2로 돌아간다.
5. 최후의 한명이 승리한다.

정수 n과 k가 주어진다. 게임의 승자를 구하시오.

 

 

풀이

처음에는 start를 0으로 한다.

단순히 배열에 1부터 n까지 순차적으로 요소를 넣고, 각 단계마다 다음을 따른다:

idx = (start + k) % arr.size()로 다음 탈락시킬 친구위치를 구한다.

배열의 idx번째 친구를 삭제한다.

다음 start는 idx로 한다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int findTheWinner(int n, int k) {
        vector<int> arr(n, 0);
        for(int i = 0; i < n; i++) {
            arr[i] = i+1;
        }

        int start = 0;
        k--;
        while(arr.size() > 1) {
            int idx = (start + k) % arr.size();
            arr.erase(arr.begin()+idx);
            start = idx;
        }
        return arr[0];
    }
};