구현으로 분류되어 있던 실버4 난이도의 문제이다.

접근

처음에는 문제가 이해가 잘되지 않았다. 예제의 경우 원형으로 앉아있고, 처음에 3번째 사람을 제거하면 다음에는 1,2,4,5,6,7 순서이므로 4번째 사람이 제거되어야하지 않나? 라는 생각이었다.

천천히 예제를 보며 생각해보니 3번 사람을 제거했으면 그 다음인 4번 사람부터 순서를 세어 4,5,6 즉 6번 사람이 제거되는 것이었다.

어떻게 풀까?

처음 생각한 것은 일반적인 정수형 배열에 값들을 넣고 반복문을 돌리는 것이었다. 3번 사람을 제거하고 arr[2]는 비우고, 다음 인덱스인 3번을 저장해뒀다가 다시 3명을 카운트해서 비워주는 방법을 생각했는데 너무 비효율적이고 코드가 지저분해질 거 같았다.

그러다가 전에 개념정리한 큐가 생각났다.
큐에 값들을 넣고, 3번째 전까지 즉 첫번째와 두번째는 poll하여 제일 뒤로 offer 메서드로 넣어주는 것이다. 그리고 세번째 값은 poll하고 stringBuilder에 append 해주고 값을 poll로 제거하는 것이었다.

코드는 아래와 같다.

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


public class Main {

    private static int N;
    private static int K;
    private static Queue<Integer> q = new LinkedList<>();


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

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

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

        sb.append('<');

        while (!q.isEmpty()) {
            for (int i = 0; i < K - 1; i++) {
                q.offer(q.poll());
            }
            if (q.size() == 1) {
                sb.append(q.poll()).append(">");
            } else {
                sb.append(q.poll()).append(", ");
            }
        }
        System.out.println(sb);
    }
}