백준 1158 - 요세푸스

문제 파악

사람을 제거하는 문제
N명의 사람들을 원형으로 돌려 순서대로 K번째 사람을 한 명씩 제거

큐를 사용하는 이유 : 앞에서 사람을 제거하거나 남은 사람을 뒤로 보내는 작업이 선입선출의 특징을 가진 큐의 작동 방식과 같다!
스택이 안되는 이유 : 순서를 유지하기 어렵다.

풀이

1. N명의 사람, K 번째 사람을 죽이기 위해 입력을 받는다.
2. 1번부터 N번까지 큐에 넣는다.
3. 큐가 빌 때까지 사람을 제거한다.
   a. K가 되기 전까지 큐에서 하나씩 pop 해서 다시 add
   b. K에 도달하면 K번째 사람을 제거
   c. 스트링 빌더에 제거한 사람 넣어주기

코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // 사람 수
        int K = sc.nextInt(); // 제거 간격

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            queue.add(i); // 1번부터 N번까지 큐에 넣음
        }

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

        while (!queue.isEmpty()) {
            // K-1번은 맨 앞을 뒤로 보냄
            for (int i = 0; i < K - 1; i++) {
                queue.add(queue.poll()); // 앞에 있는 걸 꺼내서 뒤로 보냄
            }

            // K번째 사람 제거
            sb.append(queue.poll());

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

        sb.append(">");
        System.out.println(sb.toString());
    }
}