[BOJ] 1158번 요세푸스 문제 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    static int N, K, cnt;
    static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb;

    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder("<");

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= N; i++) {
            q.add(i);
        }

        while (!q.isEmpty()) {
            int now = q.poll();
            cnt++;

            if (cnt == K) {
                cnt = 0;
                sb.append(now).append(", ");
            } else {
                q.add(now);
            }
        }

        sb.delete(sb.length() - 2, sb.length())
                .append(">");
        System.out.println(sb);
    }
}

📄 해설

접근

• 큐를 사용하여 맨 앞의 원소를 뒤로 보내면서 K 번째에 해당하는 원소는 출력하면 되는 문제로, 큐를 활용한 대표적인 문제라고 할 수 있겠다.
• 문제에서 이미 풀이를 알려줬으므로 바로 풀이과정을 설명하도록 하겠다.

과정

• 사실 접근과 크게 다르지 않다. 1부터 N 까지의 숫자를 큐에 넣고, 큐가 빌 때까지 큐에서 원소를 빼내면서 아래 과정을 반복한다.
• cnt 값을 증가시키고, 이 값이 K 와 같을 경우 cnt 값을 초기화하고 빼낸 원소를 출력한다. 이때, 바로 출력하지 않고 StringBuilder 를 사용하였다.
• K 번째 숫자가 아닌 경우 다시 큐에 넣고 반복한다.
• 마지막 부분은 출력문 조정 부분으로, 따로 설명하지는 않겠다.
• 위 코드에서 큐의 구현체로 원래 LinkedList 를 사용했는데, 다른 사람들의 풀이를 찾아보던 중 LinkedList 대신 ArrayDeque 를 사용할 경우 시간이 약간 줄어든것을 확인할 수 있었다. (100ms 정도)