요세푸스 문제

문제 풀러가기

1158

코드

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

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

    Deque<Integer> dq = new ArrayDeque<>();

    StringBuilder sb = new StringBuilder("<");
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");

    int n = Integer.parseInt(st.nextToken());
    int k = Integer.parseInt(st.nextToken());

    for(int i = 0; i < n; i++) {
      dq.add(i);
    }

    while(!dq.isEmpty()) {
      for(int i = 0; i < k - 1; i++) {
        dq.addLast(dq.removeFirst());
      }

      sb.append(dq.removeFirst() + ", ");
    }

    System.out.print(sb.toString().substring(0, sb.length() - 2));
  }
}

설명

데크를 사용했다. 요세푸스 순열에서는 k번째 숫자를 제거한 후에 처음으로 돌아가는 것이 아니라 제거된 자리가 시작지점이 된다. 입력받은 길이만큼 데크를 채우고 K번째 숫자(인덱스는 K - 1)가 나올 때까지 앞에 숫자를 맨 뒤로 보낸다. 해당 위치에 있는 수를 StringBuilder에 채우고 모든 수가 사라질 때까지 반복한다.