[JAVA] 백준 11866_요세푸스 문제 0

 

[문제링크]

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

 

📌 문제 탐색하기

1부터 N까지 사람들이 원형으로 앉아있는 상태에서 K번째 사람을 제거하고 그 다음 K번째 사람을 계속 제거한다. 

모든 사람이 제거될 때까지 해당 과정을 반복하면서 제거된 순서를 출력하는 문제이다.

 

📌 가능한 시간복잡도 

각각 요소를 제거할때는 최대 k-1번 이동하고 제거하는 과정을 반복하는 상황이기때문에... 

따라서 가능한 시간복잡도는 O(N * K) 입니다.

 

📌 코드 설계하기

1. N과 K의 값을 입력받는다. 

 

원형으로 앉아있는 형태에서 특정 순서의 사람을 제거하는 과정을 진행해야하니까... 큐 사용해서 순열처리하는게 깔끔할거같음. 

2. 1~N까지 번호를 큐에 추가한다.

3. 순열 계산하기 ( 요세푸스 순열... )

4. 출력 형식 맞추기 ( 출력 형식 제대로 안맞춰서 한번 틀림 ) 

 

📌 정답 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

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

        int n = scanner.nextInt(); 
        int k = scanner.nextInt(); 
        scanner.close();

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            queue.add(i);
        }

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

        while (!queue.isEmpty()) {
            // K-1번 앞으로 이동
            for (int i = 0; i < k - 1; i++) {
                queue.add(queue.poll()); // 맨 앞의 요소를 맨 뒤로 이동
            }

            // K번째 사람 제거
            result.append(queue.poll());
            if (!queue.isEmpty()) {
                result.append(", "); // 마지막 요소가 아닐 경우 쉼표 추가
            }
        }
        result.append(">");
        System.out.println(result);
    }
}