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

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

Find the Winner of the Circular Game - LeetCode

 

 

 

1. 문제 설명 

유명한 요세푸스 문제이다. n과 k가 주어질 때, k번째 사람들을 제거해서 마지막에 남은 수를 반환하라.

 

 

 

2. 접근 방식 

모듈러 연산으로 접근했다. j = 0(시작위치)부터 + k(제거할 위치) - 1(0번째 인덱스부터 시작)부터 % len(q)를 해주면서 해당하는 위치의 수를 제거해주었다. len(q)가 1이 되면 q에 남은 수를 반환해준다. 큐를 이용해 반복적인 pop과 push를 이용해도 짤 수 있다. 하지만 속도가 많이 느리다. 백준에서 https://www.acmicpc.net/problem/1158 문제를 풀다보면 동일한 유형이지만 큐를 활용한 방법은 시간 초과가 나고 모듈러 연산을 통한 방법은 AC를 받는다. 유의하자!

 

 

 

3. 주석 달기 (변수 설명, 각 줄마다 문장으로 설명, 함수 설명)

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        q = [i for i in range(1,n+1)]
        j = 0 
        while len(q) > 1 :
            j = (j+k-1) % len(q)
            q.pop(j)
        return q[0]

 

 

4. 분석 및 시간복잡도 

시간복잡도 : O(N)