LeetCode 1823 solution

problem

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.

python

from collections import deque
class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        l = deque([x for x in range(1,n+1)])
        if len(l) == 1:
            return l[0]
        else:
            while len(l) > 1:
                l.rotate(-(k-1))
                l.popleft()
            return l[0]

원형 큐에서는 역시나 deque 사용하는 것이 속이 편하다. 다른 것은 확인할 것이 없으나 중요한 것은 l.rotate(+), l.rotate(-)의 차이는 알아놓아야 한다. + 일 경우에는 오른쪽으로 회전한다. 즉 l.appendlef(l.pop())과 같은 식으로 행동하게 된다. 반면에 - 일 경우에는 l.append(l.popleft())처럼 왼쪽으로 회전하게 된다.

deque를 사용하는 것의 가장 큰 이유는 0-index에 뭐를 놓을지를 편하게 하려는 것이다. popleft()라는 다른 자료구조에 비하면 굉장히 시간복잡도에서 우위를 가져올 수 있는 특징 때문에 이것을 이용하는 것이 유리하다. 해당 문제에서는 회전을 주어진 횟수만큼 하다가 마지막에 popleft를 해당 경우에 하기 위해서 deque를 사용하였다.