[JAVA] 백준 11866번: 요세푸스 문제 0

백준

[JAVA] 백준 11866번: 요세푸스 문제 0

스파게티 코더 2024. 7. 16. 16:35

문제

1번부터 N번까지 사람들이 원을 이루고 앉아있고 순서대로 K번째 사람을 제거하며 모든 사람이 제거될 때까지 반복할 때, 제거되는 순서(요세푸스 순열)를 출력하는 문제.

아이디어

큐를 이용해 문제 내용을 그대로 구현할 수 있다.
- 큐를 선언하고 1 ~ N 을 저장한다.
- 큐의 가장 첫번째 사람을 뒤로 옮기며 이 과정을 K-1번 반복한다.
- 반복 이후 큐의 가장 첫번째 사람이 우리가 제거해야 하는 K번째 사람이므로 제거하고 출력한다.
- 이 과정을 큐에 사람이 없을 때까지(큐가 빌 때까지) 반복한다.

풀이

import java.io.*;
import java.util.*;

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());
        
        // 큐 선언
        Deque<Integer> deque = new ArrayDeque<>();
        
        // 큐에 1 ~ N번째 사람 추가
        for(int i=1; i<N+1; i++) {
            deque.addLast(i);
        }

        sb.append('<');

        while(true) {
            // 큐의 가장 앞 사람을 큐의 맨 뒤로 옮김
            for(int i=0; i<K-1; i++) {
                deque.addLast(deque.removeFirst());
            }
            
            // K번째 사람 제거
            sb.append(deque.removeFirst());
            
            // 큐가 비었다면(모든 사람을 제거했다면) 탈출
            if(deque.isEmpty()){
                sb.append('>');
                break;
            }
            sb.append(", ");
        }

        System.out.println(sb);
    }
}

채점 결과

기타

큐를 이용해 문제를 그대로 구현하는 느낌이 재미있었다.

문제 링크

11866번: 요세푸스 문제 0 (acmicpc.net)