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

이 글은 읽는데 약 4분이 걸립니다.

※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.

문제

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

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)

출력

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

요세푸스 문제란

문제에서도 설명되어 있듯이 원탁에 사람들이 앉아있고, 첫 번째 사람부터 K번째 사람을 제거한다. 이후 제거된 사람부터 또 K번째 사람을 제거하고… 이것을 모든 사람이 제거될 때 까지 반복하며, 사람이 제거되는 순서를 순서대로 출력해내는 것이 이 문제이다.

위와 같이 이미 제거된 번호는 건너뛰면서 K만큼 이동 후 해당 번호도 제거하는 식이다.

풀이

여기서는 큐를 이용할 것이며, 큐는 먼저 들어온 값이 먼저 나간다. 이 특징을 이용해 원형으로 배치된 번호를 구현해서 회전시키는 것을 구현할 수 있다.

덱의 앞에서부터 번호를 순서대로 추가한 후, 3만큼 움직인다를 가정하면 앞의 값을 빼서 뒤에 추가하는 식으로 두 번 반복하면 앞자리에는 세 번째 움직였을 때 나올 값이 나오게 된다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();

String[] input = br.readLine().split(" ");
int N = Integer.parseInt(input[0]);
int K = Integer.parseInt(input[1]);

Queue<Integer> queue = new LinkedList<>();  // LinkedList로 큐를 만든다
for(int i=1; i<=N; i++){
    queue.add(i);  // 큐에 1부터 N까지 번호를 순서대로 추가한다
}

sb.append("<");
for(int i=0; i<N-1; i++){  // N-1번 반복한다. 그러면 마지막에는 큐에 한 개의 값만 남는다
    for(int j=0; j<K-1; j++){  // 이동횟수-1번 이동한다.
        int num = queue.poll();  // 첫번째 값을 꺼내서
        queue.add(num);  // 뒤에 추가(=한 번 이동)
    }
    int die = queue.poll();  // 원탁에서 K번 이동 후 제거될 사람의 번호가 제일 앞에 와있는 상태이므로 꺼낸다
    sb.append(die).append(", ");  // 출력에 추가
}
sb.append(queue.poll());  // 큐에 한 명만 남았으므로 마지막으로 그것도 꺼내서 출력에 추가
sb.append(">");

System.out.println(sb.toString());
br.close();

댓글