[백준 자바] 요세푸스 문제(1158, 11866)

실버

문제

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

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)

출력

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

 

---

 

728x90

1. 원형 큐(링 버퍼)를 사용

• 먼저 1부터 N까지의 사람을 큐에 추가하여 초기화한다.
• K번째 요소의 앞에 있는 모든 요소 즉 K-1개의 요소를 큐의 끝으로 이동시킨다.
• K번째 요소를 큐에서 제거한다.
• 큐가 빌 때까지 반복한다.

큐	출력
1 2 3 4 5 6 7
4 5 6 7 1 2	3
7 1 2 4 5	3 6
4 5 7 1	3 6 2
1 4 5	3 6 2 7
1 4	3 6 2 7 5
4	3 6 2 7 5 1
	3 6 2 7 5 1 4

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

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

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

    StringBuilder sb = new StringBuilder();
    sb.append('<');

    while (!q.isEmpty()) {
      for (int i = 0; i < K - 1; i++) {
        q.add(q.remove());
      }
      sb.append(q.remove());
      if (!q.isEmpty()) {
        sb.append(", ");
      }
    }

    sb.append('>');

    bw.write(sb.toString());

    bw.flush();
    br.close();
    bw.close();
  }
}

2. 리스트 사용

• 1부터 N까지의 사람을 리스트에 저장한다.
• 현재 제거할 사람의 인덱스 변수를 생성한다(index). 사람 N은 인덱스 N-1에 위치하기 때문에 초기값은 K-1로 설정한다. 
• index위치의 사람을 제거하고 다음 제거할 위치를 결정하기 위해 index에 K-1을 더한다.
• index가 리스트의 크기보다 클 경우 index를 리스트의 크기만큼 나눈 나머지를 index로 설정한다.
• 리스트가 빌 때까지 반복한다.

index	list	출력
	1 2 3 4 5 6 7
2	1 2 3 4 5 6 7	3
4	1 2 4 5 6 7	3 6
6 -> 1	1 2 4 5 7	3 6 2
3	1 4 5 7	3 6 2 7
5 -> 2	1 4 5	3 6 2 7 5
4 -> 0	1 4	3 6 2 7 5 1
2 -> 0	4	3 6 2 7 5 1 4

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

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

    List<Integer> list = new ArrayList<>();
    for (int i = 1; i <= N; i++)
      list.add(i);

    StringBuilder sb = new StringBuilder();
    sb.append('<');

    int index = K - 1;
    while (!list.isEmpty()) {
      if (index >= list.size())
        index %= list.size();

      sb.append(list.remove(index));
      if (!list.isEmpty()) {
        sb.append(", ");
      }

      index += (K - 1);
    }

    sb.append('>');

    bw.write(sb.toString());

    bw.flush();
    br.close();
    bw.close();
  }
}