조세푸스

풀이

문제를 이해한다면 연결 리스트로 풀어야 한다는 생각이 딱 들것입니다. 리스트의 중간 요소를 하나씩 제거하는 연산을 효율적으로 처리할 수 있는 자료구조가 연결 리스트이기 때문입니다.

구현

import java.util.*;

public class Main {

    public static int N, K;
    public static LinkedList<Integer> people;

    public static void input(Scanner scanner) {
        N = scanner.nextInt();
        K = scanner.nextInt();
        people = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            people.add(i);
        }
    }

    public static void solve() {
        int index = 0;
        while (people.size() >= 3) {
            // 삭제전 위치에서 K칸 이동해야 하므로 index--를 실행해야 한다.
            people.remove(index--);
            // 리스트의 길이를 넘어가면 모듈라 연산으로 쉽게 처음으로 돌아갈 수 있다.
            index = (index + K) % people.size();
        }
    }

    public static void output() {
        for (int i : people) {
            System.out.println(i + " ");
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int testCase = scanner.nextInt();
        for (int i = 0; i < testCase; i++) {
            input(scanner);
            solve();
            output();
        }
    }
}

시간 복잡도 분석

반복문이 하나이므로 시간 복잡도는 $O(n)$입니다. n의 최댓값은 1000이기 때문에 당연히 시간 제한을 만족합니다.

회고

처음엔 좀더 직관적인 방법으로 해결하려고 했습니다. 그래서 ListIterator를 사용하여 해결하려고 했는데, 자바에서는 Iterator객체에서 다시 처음으로 되돌아갈 수 있는 메소드가 없어서 처음으로 돌아가야 할 때마다 ListIterator 인스턴스를 새로 만들어야 했습니다. 그리고 한 번 삭제할 때마다 K번만큼 $next()$를 호출해야 했기 때문에 시간 복잡도는 $O(nk)$였습니다.

public static void solve() {
    ListIterator<Integer> iterator = people.listIterator();
    iterator.next();
    while (people.size() >= 3) {
        iterator.remove();
        for (int i = 0; i < K; i++) {
            if (!iterator.hasNext()) {
                iterator = people.listIterator();
                iterator.next();
            } else {
                iterator.next();
            }
        }
    }
}

시뮬레이션 형식으로 구현하는 것이 직관적이긴 하나, 더 효율적인 방법으로 구현할 수 있어서 그렇게 했습니다.