JAVA 백준 11866 요세푸스 문제 0 (큐)

 

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

---

문제

1. 첫째 줄에 사람의 수 N과 양의 정수 K가 주어진다. ( 1 <= K <= N <= 1000 )
2.  1번부터 N번까지의 사람이 원을 이루고 앉아있을 때, 1번부터 시작하여 반복적으로 K번째 사람을 제거하며 모든 사람이 제거될 때까지 반복하면 된다.

---

 

 

초기 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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

        Queue<Integer> queue = new LinkedList<>();

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= N; i++) {
            queue.offer(i);
        }

        StringBuilder sb = new StringBuilder();

        sb.append("<");

        while (!queue.isEmpty()) {
            if (queue.size() >= K) {
                for (int i = 0; i < K-1; i++) {
                    queue.offer(queue.poll());
                }
                sb.append(queue.poll());
            }else{
                sb.append(queue.poll());
            }

            if (!queue.isEmpty()){
                sb.append(", ");
            }
        }

        sb.append(">");

        System.out.println(sb);
    }
}

 

문제를 잘못 이해해서 틀린 것 같다.

 

문제 이해를 큐에서 K - 1번째 수까지 front로 빼서 다시 뒤로 삽입하는 동작을 큐의 크기가 K보다 클 동안 반복한 후 K번째 수를 큐에서 삭제하며 출력하고,

남은 수를 앞에서부터 하나씩 삭제하며 출력하는 줄 알았다.

 

 

제대로 만들었다고 생각하고 제출했더니 아예 문제 해석부터 틀려서 바로 틀렸다.

 

반례를 찾아 문제를 다시 해석해보니

큐에서 K - 1번째 수까지 앞으로 빼서 뒤로 삽입하고 K를 출력하는 것을 반복하면 되는 거였다.

 

 

최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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

        Queue<Integer> queue = new LinkedList<>();

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        for (int i = 1; i <= N; i++) {
            queue.offer(i);
        }

        StringBuilder sb = new StringBuilder();

        sb.append("<");

        while (!queue.isEmpty()) {
            for (int i = 0; i < K - 1; i++) {
                queue.offer(queue.poll());
            }
            sb.append(queue.poll());

            if (!queue.isEmpty()) {
                sb.append(", ");
            }
        }

        sb.append(">");

        System.out.println(sb);
    }
}