[TIL] 백준 11866번 요세푸스 문제 0

문제

해결 방법

• 1부터 N까지 정해진 순서대로 나열되어 있고, 순서대로 K번째 수를 만나면 해당 숫자를 나열 되어 있는 곳에서 제거한 후, 임의의 공간에 저장한다.
• 남아있는 숫자로 멈춘 지점부터 다시 K번째 수를 찾는다.

Queue는 선입선출의 방식을 따르기 때문에 데이터의 순서를 보장할 수 있다.

1. Queue에 1부터 N까지의 숫자를 저장한다.

2. 1부터 K-1번째까지의 숫자를 순차적으로 Queue에서 빼내고 다시 저장한다.

   • 맨 앞에 있던 숫자를 맨 뒤로 옮겨져, 순서를 지속할 수 있다.

3. K번째의 숫자와 ", "를 함께 StringBuilber에 저장한다.

4. 2-3번과정을 queue가 비어질 때까지 반복한다.

5. 마지막 ", "을 제거한다.

6. ">" 꺽쇠를 추가하고 반환한다.

구현 코드

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());

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

        // 큐에 n번쨰까지 값을 넣고
        Queue<Integer> que = new LinkedList<>();
        for(int i = 1; i <= n; i++){
            que.add(i);
        }

        while (!que.isEmpty()) {
            // k-1번째 까지 값을 빼 큐에 맨뒤에 저장
            for(int i = 0; i < k-1; i++) {
                int tmp = que.poll();
                que.add(tmp);
            }
            // k번째 숫자는 빼서 result에 저장
            sb.append(que.poll() + ", ");
        }

        sb.delete(sb.length()-2, sb.length());
        sb.append(">");
        System.out.println(sb);
    }
}