CodeWars 아흔 세 번째 문제

Josephus Survivor

public static int josephusSurvivor(final int n, final int k) {

    List<Integer> list = initialList(n);

    return survivor(list, k);
}

private static int survivor(List<Integer> list, int k) {
    int pos = 0;

    while(list.size() > 1) {

        pos += k-1;

        if(pos >= list.size()) {
            pos = pos % list.size();
        }

        list.remove(pos);
    }

    return list.get(0);
}

private static List<Integer> initialList(int n) {

    List<Integer> list = new ArrayList<Integer>();

    for(int i = 1; i <= n ; i++) {
        list.add(i);
    }

    return list;
}

• 문제가 의도한(?) 대로 정석(?)적으로 해결했다.
• 해당 위치에서 다음 이동할 위치가 list의 사이즈보다 크다면 사이즈만큼 나눈 나머지가 해당 위치가 된다.
• 그러나 Best 코드는… 정말로 간단하게 풀었다.
• Best 코드에 대해서 연구해도 왜 저런 식(?)이 나왔는지 이해가 안간다…
• 이건 어쩔수 없는 머리의 한계인가

Best Code

public static int josephusSurvivor(final int n, final int k) {
    if(n == 1)
        return 1;

    return (josephusSurvivor(n - 1, k) + k - 1) % n + 1;
} 

public static int josephusSurvivor(final int n, final int k) {
    int remaining = 0;
    
    for (int i = 2; i <= n; i++) {
        remaining = (remaining + k) % i;
    }

    return remaining + 1;
}