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

문제 링크

---

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

접근 방법

---

요세푸스 순열을 구하는 문제로, 사람들을 원형으로 배열한 뒤, k번째 사람을 제거해 나가며 순열을 구성합니다.
LinkedList를 이용해 인덱스를 조정하며 반복적으로 사람을 제거하면 됩니다.

순차적으로 진행하되, 매번 현재 인덱스에 k를 더하고 리스트 크기만큼 나머지 연산을 해 다음 제거할 위치를 구합니다.

소스 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]), k = Integer.parseInt(s[1]) - 1;

        List<Integer> arr = new LinkedList<>();
        List<Integer> rst = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            arr.add(i);
        }

        int i = 0;
        while (!arr.isEmpty()) {
            i = (i + k) % arr.size();
            rst.add(arr.get(i));
            arr.remove(i);
        }

        System.out.println(
            rst.toString()
                .replace('[', '<')
                .replace(']', '>')
        );
    }
}

코드 설명

---

1부터 n까지 사람을 리스트에 담고, k번째 인덱스를 계속 순회하면서 제거합니다.
리스트에서 원소를 제거할 때마다 인덱스를 업데이트하며 반복하고, 최종 결과를 출력 형식에 맞게 <> 괄호로 출력합니다.