[algospot] 조세푸스 문제 (연결리스트)

기본 자료구조 중 하나인 연결리스트를 정리하기 위해 알고리즘 문제를 풀어보았다.

algospot의 조세푸스 문제이다. (링크)

문제를 간략히 요약하면 원으로 둘러싸인 병사들이 하나씩 죽는데, k번의 간격을 두고 순차적으로 죽으며 나머지 2명을 찾아내는 문제이다.

원으로 모여있다고 가정하기 때문에 연결리스트의 마지막 다음이 첫번째 연결리스트 노드로 인식하고 풀어나가면 된다.

Java에서는 연결리스트의 표준 라이브러리로 LinkedList를 구현해 놓았다.

LinkedList의 iterator(링크)로 노드들을 순차적으로 탐색할 수 있다.

문제를 풀면서 LinkedList에 대해서 정리를 추가로 한 부분.

• iterator()로 얻은 첫 노드는 LinkedList의 첫 노드가 아니라 첫 노드를 가르키는 head이다.
• 문제에서 풀 때 iterator()를 호출 후 첫 노드를 제거하기 전에 next()로 첫 노드로 이동을 먼저한다.
• 요소의 변환이 일어날 경우, iterator를 사용해야 한다. (effective java 규칙 46. 참조)

[[답안]]

import java.io.*;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

public class Josephus {

    private static BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        int cases = Integer.parseInt(stdin.readLine());

        while (cases-- > 0) {
            String[] data = stdin.readLine().split(" ");
            int last = Integer.parseInt(data[0]);
            int step = Integer.parseInt(data[1]);

            writer.append(josephus(last, step));
            writer.newLine();
        }

        writer.flush();
        writer.close();
    }

    private static String josephus(int n, int k) {

        List<Integer> list = new LinkedList<>();
        for (int i = 1; i <= n; ++i) {
            list.add(i);
        }

        Iterator<Integer> iterator = list.iterator();
        iterator.next();

        while (n > 2) {
            iterator.remove();
            if (!iterator.hasNext()) {
                iterator = list.iterator();
            }
            iterator.next();
            --n;

            for (int i = 0; i < k-1; ++i) {
                if (!iterator.hasNext()) {
                    iterator = list.iterator();
                }
                iterator.next();
            }
        }
        return list.stream().map(String::valueOf).collect(Collectors.joining(" "));
    }
}