[Baekjoon] 1158번: 요세푸스 문제 - Java

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

1158번: 요세푸스 문제

풀이 방법 1. Queue

먼저 모든 사람을 큐에 넣고 K - 1만큼 빼고 다시 큐에 넣는다. 그 후에 빼는 사람은 K 번째가 되므로 큐가 빌 때까지 이 과정을 반복하는 식으로 해결했다. 시간 복잡도는 O(N * K) 이다.

while (!queue.isEmpty()) {
    IntStream.rangeClosed(1, K - 1).forEach(idx -> queue.add(queue.remove()));
    ans.add(queue.remove());
}

풀이 방법 2. ArrayList

지울 사람만 선택해서 지우는 방식으로도 해결할 수 있다. 이 방법이 큐를 활용한 방법보다 시간적으로나 공간적으로나 더 효율적인 것으로 나타났다. 시간 복잡도는 O(n)이다.

while (list.size() != 1) {
    remove = (remove + K - 1) % list.size();
    sb.append(list.get(remove)).append(", ");
    list.remove(remove);
}

전체 코드는 다음과 같다.

package baekjoon.queue;

import java.io.*;
import java.util.*;
import java.util.stream.IntStream;

public class BOJ1158 {

    static int[] input;
    static int N;
    static int K;
    static List<Integer> list;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            input = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            N = input[0];
            K = input[1];

            list = new ArrayList<>();
            IntStream.rangeClosed(1, N).forEach(list::add);

            sb.append("<");
            int remove = 0;
            while (list.size() != 1) {
                remove = (remove + K - 1) % list.size();
                sb.append(list.get(remove)).append(", ");
                list.remove(remove);
            }
            sb.append(list.get(0)).append(">");

            System.out.print(sb);
        }
    }
}