[자료구조] 백준 1158 요세푸스 문제

1158번: 요세푸스 문제

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

 

# 코드

import java.io.*;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // 빠른 입출력을 위한 BufferedReader 와 BufferedWriter
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 문자열 분리를 위한 StringTokenizer
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        // N, K
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        // N명의 사람을 담는 LinkedList
        LinkedList<Integer> n_list = new LinkedList<>();

        // 1 ~ N 값을 리스트에 삽입
        for (int i = 1; i <= n; i++) {
            n_list.add(i);
        }

        bw.write("<");
        // 사람이 모두 제거될 때까지 반복 (=N번 반복)
        for (int i = 0; i < n; i++) {
            // 첫 번째 출력을 제외하고 콤마 찍기
            if (i != 0) {
                bw.write(", ");
            }

            // k - 1 번째 (1번째부터 시작하므로) 사람을 찾아 제거하는 과정
            for (int j = 0; j < k; j++) {
                if (j == (k - 1)) {
                    // k - 1 번째 사람이라면 출력하며 리스트에서 제거
                    bw.write(String.valueOf(n_list.remove()));
                } else {
                    // 아직 k - 1 번째 사람이 아니라면 리스트에서 제거하여 맨 뒤로 보냄
                    n_list.add(n_list.remove());
                }
            }
        }
        bw.write(">");

        // Reader 버퍼 닫기
        br.close();

        // Writer 버퍼 비운 뒤 닫기
        bw.flush();
        bw.close();
    }
}

• 1 ~ N번까지의 사람이 원을 이루며 앉아있는 상황에서 모든 사람이 제거될 때까지 K번째 사람을 연속해서 제거해야 한다.
• (N, K) - 요세푸스 순열, 즉 N과 K 값에 따라 제거되는 순서를 출력하면 되는 문제이다.
• 삽입과 삭제가 빠른 LinkedList를 이용해 구현했다.
• k - 1 번째 사람을 제거해야 한다는 점과 그 k - 1 번째 사람을 찾을 때까지 리스트의 가장 앞 원소를 하나씩 빼서 맨 뒤로 보내는 과정이 문제 풀이의 핵심이었다.
• removeFirst() 를 사용하면 더욱 직관적이겠으나, remove() 메소드에 인수를 작성하지 않을 경우 기본적으로 LinkedList의 첫 번째 요소를 제거하므로 동일하게 사용할 수 있다. (두 경우 모두 정답 처리됨)