[CLASS 2: 자료구조] 백준 11866 요세푸스 문제(0)

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

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

 

# 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        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());

        ArrayDeque<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            q.addLast(i);
        }

        // 사람이 모두 제거될 때까지 반복
        while (!q.isEmpty()) {
            // k번째 사람 제거
            for (int j = 1; j <= k; j++) {
                if (j == k) { // k번째 사람이면 제거
                    if (sb.length() == 0) { // 첫 번째 삽입일 경우
                        sb.append("<" + q.removeFirst());
                    } else {
                        sb.append(", " + q.removeFirst());
                    }
                } else { // k번째 사람이 아니면 제거하지 않고 가장 뒤로 보냄
                    q.addLast(q.removeFirst());
                }
            }
        }
        sb.append(">");
        System.out.println(sb);
        br.close();
    }
}

• 이전에 요세푸스 문제를 풀어본 적이 있어 어렵지 않게 푼 문제였다.
• LinkedList를 사용했던 이전과 달리 ArrayDeque를 사용해 훨씬 좋은 성능을 얻어냈다. (～￣▽￣)～

 

 

ArrayDeque 사용

LinkedList 사용

 

 

 

👇🏻 이전 요세푸스 풀이가 궁금하다면 👇🏻

[자료구조] 백준 1158 요세푸스 문제