요세푸스 문제

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.stream.IntStream;

public class Main {
    static public class Node {
        private int value;
        private Node nextNode;
        private Node prevNode;
        public Node() {}
        Node(int val) {
            value = val;
        }
        Node(int val, Node next) {
            value = val;
            nextNode = next;
        }
        Node(int val, Node next, Node prev) {
            value = val;
            nextNode = next;
            prevNode = prev;
        }
    }

    static private class JosephusRing {
        Node baseNode;
        Node currentNode;

        final int strideInterval;

        JosephusRing(int interval) {
            strideInterval = interval;
            baseNode = new Node();
            currentNode = new Node();
        }

        public void build(int size) {
            IntStream.iterate(1, x -> x + 1).limit(size).forEach(x -> {
                if (x == 1) {
                    baseNode = new Node(1);
                    currentNode = baseNode;

                    if(x == size) {
                        currentNode.nextNode = baseNode;
                        baseNode.prevNode = currentNode.nextNode;
                    }
                }
                else if (x == size) {
                    currentNode.nextNode = new Node(x, baseNode, currentNode);
                    baseNode.prevNode = currentNode.nextNode;
                    currentNode = currentNode.nextNode;
                }
                else {
                    currentNode.nextNode = new Node(x, null, currentNode);
                    currentNode = currentNode.nextNode;
                }
            });
        }
        
        public void consume() {
            currentNode = baseNode;
            System.out.print("<");
            for (int i = 1; ; ++i) {
                if (i % strideInterval == 0) {
                    if (currentNode == currentNode.nextNode) {
                        System.out.format("%d", currentNode.value);
                        break;
                    }
                    currentNode.prevNode.nextNode = currentNode.nextNode;
                    currentNode.nextNode.prevNode = currentNode.prevNode;
                    System.out.format("%d, ", currentNode.value);
                    currentNode = currentNode.nextNode;
                }
                else {
                    if (currentNode == currentNode.nextNode) {
                        System.out.format("%d", currentNode.value);
                        break;
                    }
                    currentNode = currentNode.nextNode;
                }
            }
            System.out.println(">");
        }
        
    }

    static public void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        int numberOfPeople = Integer.parseInt(st.nextToken());
        int interval = Integer.parseInt(st.nextToken());
        bf.close();

       JosephusRing josephusRing = new JosephusRing(interval);
       josephusRing.build(numberOfPeople);
       josephusRing.consume();
    }
}

코드 바로가기
http://boj.kr/bc4a4e49c31d4db9a50e1735fb44c1c9

썸네일 출처 https://medium.com/carwow-product-engineering/the-josephus-problem-2ef02b77ada9