[Baekjoon] 11866 요세푸스 문제0 - JAVA

문제

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

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)

출력

예제와 같이 요세푸스 순열을 출력한다.

예제 입력 1 복사

7 3

예제 출력 1 복사

<3, 6, 2, 7, 5, 1, 4>

 

---

✏️ 제출 답안

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            queue.add(i);
        }

        StringBuilder sb = new StringBuilder();
        sb.append("<");
        while (!(queue.size() == 1)) {
            for (int i = 0; i < k-1; i++) {
                int temp = queue.poll();
                queue.offer(temp);
            }
            sb.append(queue.poll()).append(", ");
        }

        sb.append(queue.poll()).append(">");
        System.out.println(sb);
    }
}

 

 

이번 문제는 queue 알고리즘을 사용했다. 먼저 순서대로 1부터 N까지의 수를 queue에 저장한다. 그리고 k-1번까지는 값을 삭제(poll)하고 다시 넣는 작업(offer)을 반복하고 k번째에서는 그 값을 삭제하면서 반환함과 동시에 StringBuilder로 문자열에 추가해준다. queue의 size가 1이 되기 전까지 이 작업을 반복하고, queue에 원소가 하나 남았을 때는 while문을 탈출해서 마지막 값을 문자열에 추가해준 뒤 문자열을 최종적으로 출력해주면 프로그램이 종료되는 흐름이다.

 

🪄 poll vs. remove

이때 poll()은 remove() 대신 사용한 것이다. remove()와의 차이점은

remove()는 큐의 첫번째 원소를 삭제하는데 원소값이 없을 시에 예외를 던진다.

반면 poll()은 큐의 첫번째 원소를 삭제하는데 원소값이 없을 시에 예외를 던지지 않고, false를 반환한다.

 

🪄 offer vs. add

offer()는 add() 대신 사용한 것인데, add()와의 차이점은

add()는 queue에 값을 삽입할 때 오버플로가 발생했을 때 예외를 던진다.

반면 offer()는 값을 삽입할 때 큐가 가득 찬 경우에 예외를 던지지 않고, false를 반환한다. 

 

제출 현황