99클럽 코테 스터디 25일차 TIL [LeetCode] Find the Winner of the Circular Game (Java)

문제

[LeetCode] Find the Winner of the Circular Game

틀린 코드

class Solution {
    public int findTheWinner(int n, int k) {
        int cnt = 1;
        int now = 0;
        while(cnt != n) {
            now = (now + k) % n;
            cnt++;
        }
        return now;
    }
}

틀린 이유

now가 변동되면 그 인덱스의 친구를 제거해야 하는데 제거하지 않고 반복하게 되면서 오답을 반환하게 됨

풀이

• 정수형 리스트 friends에 1부터 n까지 정수를 추가한다.
• 현재 제거할 인덱스는 now에 저장한다.
• 1명이 남을 때까지 k만큼 뒤에 해당하는 인덱스를 제거한다.
• 마지막 승자를 반환한다.

정답 코드

class Solution {
    public int findTheWinner(int n, int k) {
        List<Integer> friends = new ArrayList<>();
        for(int i = 1; i <= n; i++) {
            friends.add(i);
        }

        int now = 0;
        while(friends.size() > 1) {
            now = (now + k - 1) % friends.size();
            friends.remove(now);
        }

        return friends.get(0);
    }
}