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

1. Input

1) int n

- 1번부터 n번까지 n명의 친구들이 시계방향 순으로 원을 그리며 앉아 있다.

2) int k

 

2. Output

1) 1번부터 시작해서 시계방향으로 k칸 뒤 친구에게 공을 주고, 그 다음 2*k칸 뒤 친구에게 공을 주는 식으로 공을 계속 전달하다 공을 2번 받는 친구가 생겼을 때 공 전달을 그만 뒀을 때, 공을 한 번도 받지 못한 친구들의 번호를 담은 배열을 반환

 

3. Constraint

1) 1 <= k <= n <= 50

2) 반환하는 배열은 오름차순으로 정렬해야 한다.

 

4. Example

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

설명:

- 1번이 2칸 뒤 친구에게 전달 -> 3번

- 3번이 4칸 뒤 친구에게 전달 -> 2번

- 2번이 6칸 뒤 친구에게 전달 -> 3번

- 3번이 공을 2번 받았으므로 한 번도 받지 못한 4번과 5번을 담아 반환한다.

 

5. Code

1) 첫 코드(2023/06/29)

class Solution {
    public int[] circularGameLosers(int n, int k) {
        boolean[] visited = new boolean[n+1];
        int i = 1, next = k;
        while(!visited[i]){
            visited[i] = true;
            i = (i+next)%n==0 ? n : (i+next)%n;
            next += k;
        }
        List<Integer> list = new ArrayList<>();
        for(i=1 ; i<=n ; i++)
            if(!visited[i]) list.add(i);
        int[] losers = new int[list.size()];
        for(i=0 ; i<losers.length ; i++)
            losers[i] = list.get(i);
        return losers;
    }
}

- 57%, 17%

2) set을 이용해서 푼 코드(2023/06/29)

class Solution {
    public int[] circularGameLosers(int n, int k) {
        Set<Integer> set = new HashSet<>();
        int i = 1, next = k;
        while(!set.contains(i)){
            set.add(i);
            i = (i+next)%n==0 ? n : (i+next)%n;
            next += k;            
        }
        int[] losers = new int[n-set.size()];
        i = 0;
        for(int j=1 ; j<=n && i<losers.length ; j++)
            if(!set.contains(j))
                losers[i++] = j;
        return losers;
    }
}

- 57%, 20%

- 별 다를 게 없다.