[BOJ 백준] 1158: 요세푸스 문제 (자바 | Java)

[BOJ 백준] 1158: 요세푸스 문제

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

1. 문제

• LinkedList를 이용해 풀이한다.

---

2. PS

요세푸스 순열

문제만을 읽고서는 이해가 잘 되지 않아 따로 찾아 보았다.
먼저, 문제에서는 인원의 수 n과 k번 째를 제공 해주었다. 예시로, 7명의 인원을 시작으로, 3번 째 사람을 계속해서 제거한다. 처음엔 3번 째, 그리고 3번 째에서 또 다시 3번 째 즉, 6번 사람이 제거되고, 6번 에서 또 다시 3 번째, 즉 2번 사람이다. 이를 바탕으로 구조를 그려보면

1 2 3 4 5 6 7
1 2 4 5 6 7	3
1 2 4 5 7	3 6
1 4 5 7	3 6 2
1 4 5	3 6 2 7
1 4	3 6 2 7 5
4	3 6 2 7 5 1
	3 6 2 7 5 1 4

위와 같은 형식으로 구현을 해보았다.

1. 한 줄을 입력 받고 StringTokenizer로 n, k를 선언해준다.
2. n명의 사람을 넣어줄 링크드리스트를 선언하고, 결과를 저장할 스트링빌더도 선언 해준다.
3. 링크드리스트에 1부터 n번 째 사람까지 넣어준다.
4. while문으로 리스트가 빌 때 까지 반복 해준다.
5. for문을 통해 k번 까지 돌며 i가 k-1과 일치 한다면 스트링빌더에 넣어주며 리스트에서 제거한다.

3. 풀이

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

public class Main {
    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();

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

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

        sb.append('<');
        while(!list.isEmpty()) {
            for (int i = 0; i < k; i++) {
                if (i == k-1) { // 1번 사람 부터 시작하기 때문에 k-1 과 매치한다.
                    if (list.size() == 1) { // 마지막 인원은 쉼표를 제외하고 넣어준다.
                        sb.append(list.remove());
                    } else {
                        sb.append(list.remove() + ", ");
                    }
                } else {
                    list.add(list.remove());
                }
            }
        }
        sb.append('>');
        System.out.println(sb);
    }
}