[릿코드] Find the Winner of the Circluar Game

문제

릿코드 1823. Find the Winner of the Circular Game

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

 

코드

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        circle = [i for i in range(1, n+1)]
        count = 1
        turn = 0

        while len(circle) != 1:
            if count == k:
                circle.pop(turn)
                count = 1
                if turn == len(circle):
                    turn = 0
                continue

            if turn >= len(circle) - 1:
                turn = 0
            else:
                turn += 1
                
            count += 1

        return circle[0]

 

풀이

circle = [i for i in range(1, n+1)]
count = 1
turn = 0

초기화 작업을 한다.

circle 배열은 1부터 n까지 게임에 참가하는 사람들의 번호를 담는다.

count는 한사람씩 차례를 이동 할때마다 1씩 증가하는 변수다.

turn은 누구 차례인지 나타내는 인덱스 변수다.

 

while len(circle) != 1:

circle 배열에서 승자 1명이 나올때까지 다음의 작업을 반복한다.

 

if count == k:
    circle.pop(turn)
    count = 1
    if turn == len(circle):
        turn = 0
    continue

if turn >= len(circle) - 1:
    turn = 0
else:
    turn += 1

count += 1

turn을 1씩 늘리다가 남아있는 사람들의 순서 중 마지막까지 왔다면 다시 처음의 사람으로 순서가 돌아갈 수 있게 0으로 설정한다.

turn을 1씩 늘리면서 count도 1씩 늘린다.

 

만약 count가 k와 같아진다면,

당시 순서의 사람은 패배이므로 해당 사람을 pop 한다.

count는 다시 1로 초기화하고

pop하고나서 turn이 남아있는 사람들 중 마지막을 가리키고 있다면, 맨 처음의 사람으로 순서를 지정하게 turn을 0으로 설정한다.

 

return circle[0]

마지막 남아있는 승자를 반환한다.

 

다른 코드

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        k = k-1
        index = 0
        li = [i for i in range(1,n+1)]
        def cal(k,index):
            if len(li) == 1:
                return li[0]
            index = (index + k)% len(li)
            del li[index]
            return cal(k,index)
        return cal(k,index)

 

풀이

k = k-1
index = 0
li = [i for i in range(1,n+1)]

 

초기화 작업을 한다.

k를 1 감소시키고

index를 0으로 초기화하고

li 배열은 1부터 n까지 숫자를 담는다.

 

def cal(k,index):
    if len(li) == 1:
        return li[0]
    index = (index + k)% len(li)
    del li[index]
    return cal(k,index)

index를 (index + k_ % len(li)로 업데이트하고

li에서 index 위치의 참가자를 삭제한다.

 

이 작업을 li에 요소가 하나만 들어있을때 까지만 재귀적으로 반복한다.

li에 승자 한명만 남는다면 그 승자를 반환한다.

 

return cal(k,index)

재귀함수 cal에서 반환된 최종 승자 한명을 반환한다.