[백준] java 11866 요세푸스 문제 0

https://www.acmicpc.net/problem/11866

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

풀이과정

두 개의 큐 자료구조를 사용하면 쉽게 풀이가 가능할 것 같다.

처음 구상한 방법은 큐 두개를 준비한 다음, 큐 A에 원소를 전부 삽입한다. 그리고 큐 A에서 원소를 pop하며 큐 B에 삽입한다. 이때, K 번째 원소는 큐 A에 삽입하지 않고 요세푸스 순열에 추가한다.

위와 같이 큐 A가 빌 때까지 큐 B로 원소를 pop하면서 요세푸스 순열을 채워나간다. 큐 A가 비게되면 이번엔 큐 B에서 큐 A로 원소를 pop하며 요세푸스 순열을 추가해나간다.

위와 같은 단계로 큐 A와 큐 B 모두 원소가 하나도 남지 않게 되었을 때까지 반복하면 요세푸스 순열을 알 수 있을 것이다.

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
		// 큐 A
        CustomLinkedList QueueA = new CustomLinkedList();
        // 큐 B
        CustomLinkedList QueueB = new CustomLinkedList();
        // 1부터 N까지 원소 추가
        for( int i = 1; i <= N; i++ )
            QueueA.add(i);

        sb.append("<");
        int count = 1;
        // 큐 A가 비어있지 않다면 true
        // 큐 A가 비어있다면 큐 B로부터 원소를 받아야하기 때문에
        // false로 변경
        boolean currentQueue = true;
        // 큐 A와 큐 B에 원소가 하나도 남지 않게 될 때까지 반복
        while( true ){
			// 큐 A가 비어있지 않다면
            if( currentQueue ){
				// count가 K로 나누어 떨어지지 않는다면
                // pop한 원소를 QueueB에 추가
                if( count % K != 0 ){
                    QueueB.add(QueueA.pop().value);
                }
                // count가 K로 나누어 떨어지면 
                // 요세푸스 순열에 추가
                else{
                    sb.append(QueueA.pop().value).append(", ");
                }
                // 큐 A가 비어있다면 currentQueue를
                // false로 변경
                if( QueueA.size == 0 )
                    currentQueue = !currentQueue;

            }
            // 큐 A가 비어있다면 else 로직 수행
            else {
				
                if( count % K != 0 ){
                    QueueA.add(QueueB.pop().value);
                }else{
                    sb.append(QueueB.pop().value).append(", ");
                }

                if( QueueB.size == 0 )
                    currentQueue = !currentQueue;

            }
			// QueueA와 QueueB에 원소가 하나도 없다면
            // 모든 요세푸스 순열을 완성하였으므로 반복문 종료
            if( QueueA.size == 0 && QueueB.size == 0 )
                break;

            count++;
        }
        // 마지막 쉼표와 공백 제거
        sb.delete(sb.length()-2,sb.length());
        sb.append(">");
        System.out.println(sb);
    }

아래 코드는 직접 구현한 이중 연결 리스트이다. 본 문제에선 삭제와 삽입이 빈번하게 이루어지기 때문에 연결 리스트를 사용하는 것이 유리할 것이라 생각했다.

    static class CustomLinkedList{
        Node firstNode;
        Node lastNode;
        int size;
        public CustomLinkedList(){
            firstNode = null;
            lastNode = null;
            size = 0;
        }
        public void add( int num ){
            if( firstNode == null ){
                Node node = new Node( num );
                firstNode = node;
                lastNode = node;
            }else {
                Node node = new Node( num );
                lastNode.nextNode = node;
                lastNode = node;
            }
            size++;
        }
        public Node pop(){
            if( firstNode == null )
                return null;
            Node node = firstNode;
            firstNode = firstNode.nextNode;
            size--;
            return node;
        }
    }
    static class Node{
        int value;
        Node nextNode;
        Node( int value ){
            this.value = value;
            nextNode = null;
        }
    }
}