[백준 | 1158] 요세푸스 문제 - Java (LinkedList 사용)

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

 

출력

---

예제와 같이 요세푸스 순열을 출력한다.

 

예제 입력

---

내 제출

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.ListIterator;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] inputData = br.readLine().split(" ");
        int N = Integer.parseInt(inputData[0]);
        int K = Integer.parseInt(inputData[1]);

        LinkedList<Integer> linkedList = new LinkedList<>();
        for (int i = 0; i < N; i++) {
            linkedList.add(i + 1);
        }

        StringBuffer answer = new StringBuffer();
        ListIterator<Integer> iterator = linkedList.listIterator();
        answer.append("<");

        while (!linkedList.isEmpty()) {
            for (int i = 0; i < K; i++) {
                if (!iterator.hasNext()) {
                    iterator = linkedList.listIterator();
                }
                if (i == K - 1) {
                    answer.append(iterator.next());
                } else {
                    iterator.next();
                }
            }
            iterator.remove();
            if (!linkedList.isEmpty()) {
                answer.append(", ");
            }
        }
        answer.append(">");

        br.close();
        bw.write(answer.toString());
        bw.flush();
        bw.close();
    }
}

문제 해결 사고 과정

• 문제 이해: 1부터 N까지의 사람들이 원을 이루어 앉아 있을 때, K번째 사람을 순서대로 제거하여 요세푸스 순열을 만드는 문제라고 이해하였습니다.
• 접근 방식: 1부터 N까지의 사람들의 번호가 저장된 리스트를 선언하고, 리스트가 비어있지 않을 때까지 반복하여 K번째 사람을 제거하는 방식으로 접근하였습니다.

자료 구조 선택 이유

• 선택한 자료 구조: Linked List
• 이유 및 장점: LinkedList를 선택한 이유는 ListIterator를 사용하여 리스트를 순회하고 요소를 효율적으로 제거할 수 있어 사용하였습니다.

테스트 케이스

• 테스트 케이스 1: 입력 배열이 [1, 2, 3, 4, 5]일 때, 목표 값이 9인 서브배열은 [4, 5]입니다.
• 테스트 케이스 2: 입력 배열이 [1, 1, 1, 1, 1]일 때, 목표 값이 5인 서브배열은 [1, 1, 1, 1, 1]입니다.
• 엣지 케이스: 배열이 비어있거나, 목표 값이 배열의 총합보다 큰 경우 등도 고려합니다.

시간 및 공간 복잡도 분석

• 시간 복잡도: 이 코드는 LinkedList를 순회하면서 K번째 요소를 제거합니다. LinkedList의 ListIterator는 요소를 순회하는 데 O(N) 시간이 걸리며, K번째 요소를 제거하기 위해 반복문을 N번 실행합니다. 따라서 전체 시간 복잡도는 $O(N * K)$입니다.
• 공간 복잡도: 이 코드는 LinkedList에 N개의 요소를 저장하므로 공간 복잡도는 O(N)입니다. 추가적인 메모리 사용은 StringBuffer를 사용하여 결과 문자열을 저장하는 것에 제한되며, 이는 상수 크기 또는 O(N)의 추가 공간을 사용합니다. 하지만 공간 복잡도 분석에서 주요 요소는 리스트의 크기이므로 $O(N)$입니다.

배운점

• LinkedList와 ListIterator를 직접 사용해 이해도를 높일 수 있었습니다.