[LeetCode] 2682. Find the Losers of the Circular Game

2682. Find the Losers of the Circular Game

LeetCode

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

문제

• 두 개의 정수 n과 k가 주어졌습니다.
• n명의 친구가 원형으로 앉아 있으며 1부터 n까지 시계방향으로 번호가 매겨져 있습니다.
• 처음에는 1번 친구가 공을 갖고 있으며 i번째 턴마다 공을 갖고 있는 친구는 시계방향으로 i ⨉ k만큼 떨어져 있는 친구에게 공을 전달합니다.
• 어떤 친구가 공을 두 번 받으면 게임이 종료됩니다.
• 게임의 패자는 공을 한 번도 받지 못한 친구입니다.
• 게임이 종료된 후 패자의 번호를 오름차순으로 정렬된 배열로 반환하는 코드를 작성하세요.

예제

• Input: n = 5, k = 2
• Output: [4, 5]

풀이 과정 #1

• 빈 리스트 received를 생성합니다.
• 변수 cur_loc을 0으로 초기화하고 턴을 나타내는 변수 i를 1로 초기화합니다.
• cur_loc이 received에 포함되지 않을 때까지 다음 조건을 수행합니다.
  • cur_loc을 received에 추가합니다.
  • cur_loc을 (cur_loc + i * k) % n으로 수정합니다.
  • i에 1을 더해줍니다.
• 변수 i를 0부터 n-1까지 1씩 증가시키며 received에 포함되지 않은 i에 대해 i+1을 리스트로 생성하여 반환합니다.

코드(Python) #1

class Solution:
    def circularGameLosers(self, n: int, k: int) -> List[int]:
        received = []
        cur_loc = 0
        i = 1
        while cur_loc not in received:
            received.append(cur_loc)
            cur_loc = (cur_loc + i * k) % n
            i += 1
        return [i + 1 for i in range(n) if i not in received]

풀이 과정 #2

• n개의 False값으로 이루어진 리스트를 생성하여 변수 friends에 저장합니다.
• 변수 cur_loc을 0으로 초기화하고 턴을 나타내는 변수 i를 1로 초기화합니다.
• 현재 공을 갖고 있는 친구(friends[cur_loc])가 True가 아닐 때까지 다음 조건을 수행합니다.
  
  • 현재 공을 갖고 있는 친구(friends[cur_loc])를 True로 수정합니다.
  • cur_loc을 (cur_loc + i * k) % n으로 수정합니다.
  • i에 1을 더해줍니다.
• 변수 i를 0부터 n-1까지 1씩 증가시키며 friends[i]가 False이면 i+1을 리스트로 생성하여 반환합니다.

코드(Python) #2

class Solution:
    def circularGameLosers(self, n: int, k: int) -> List[int]:
        friends = [False for _ in range(n)]
        cur_loc = 0
        i = 1
        while not friends[cur_loc]:
            friends[cur_loc] = True
            cur_loc = (cur_loc + i * k) % n
            i += 1
        return [i + 1 for i in range(n) if not friends[i]]