출처 : https://leetcode.com/problems/find-the-winner-of-the-circular-game/description/
Find the Winner of the Circular Game - LeetCode
Can you solve this real interview question? Find the Winner of the Circular Game - 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 it
leetcode.com
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)