[백준] 11866 - 요세푸스 문제 0 (Java)

Problem

https://www.acmicpc.net/problem/11866

Approach & Logic

Queue 사용

Queue는 FIFO(First In First Out) 구조이다.
이 문제에 적용해보면,
K번째마다 수를 제거하는 것이기 때문에 K번째가 아닐때는 해당 수를 뒤로 보낸다.
{1, 2, 3, 4, 5, 6, 7} -> {2, 3, 4, 5, 6, 7, 1}
{2, 3, 4, 5, 6, 7, 1} -> {3, 4, 5, 6, 7, 1, 2}
{3, 4, 5, 6, 7, 1, 2} -> 3 출력
.....

StringBuilder 사용

이 문제는 출력이 좀 특이하다.
<3, 6, 2, 7, 5, 1, 4> <- 이렇게 출력해야 하기 때문에
StringBuilder을 사용해서 값들을 추가한 후에 마지막에 한꺼번에 출력하는 방법으로 구현했다.

제거된 값을 추가할때마다 쉼표와 공백을 같이 더해주도록 구현했기 때문에

sb.append(q.poll()+", ");

while문이 끝난다음에 마지막에 추가된 쉼표와 공백을 제거해주어야 한다.

sb.deleteCharAt(sb.length() - 2);
sb.deleteCharAt(sb.length() - 1);

---

Code

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));
        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=1; i<k; i++) {
                int temp = q.poll(); //맨앞 값 빼기
                q.offer(temp); //뒤로 보내기
            }
            sb.append(q.poll()+", ");
        }


        //마지막 두문자 제거 "," & " "
        sb.deleteCharAt(sb.length() - 2);
        sb.deleteCharAt(sb.length() - 1); 
        sb.append(">");

        System.out.print(sb);
    }
}