[BaekJoon] 1158 요세푸스 문제

1.  문제 링크

2.  문제

요약

• 총 N명의 사람들이 원을 이루어 앉아있고, 양의 정수 K번째 해당하는 사람을 순서대로 제거합니다. 원에서 사람들이 제거되는 순서를 요세푸스 수열이라고 합니다.
• 입력: 사람 수에 해당하는 N과 양의 정수 K를 입력 받습니다.
• 출력: 요세푸스 수열을 출력합니다.

3.  소스코드

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

public class Main {
    public ArrayList<Integer> Josephus(int n, int k) {
        ArrayList<Integer> circle = new ArrayList<Integer>();
        ArrayList<Integer> seq = new ArrayList<Integer>();
        for(int i = 1; i <= n; i++) {
            circle.add(i);
        }
        int index = k - 1;
        while(circle.size() > 1) {
            seq.add(circle.remove(index));
            index += (k - 1);
            while(index > (circle.size() - 1)) {
                index -= circle.size();
            }
        }
        seq.add(circle.get(0));
        return seq;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input_string = br.readLine();
        StringTokenizer st = new StringTokenizer(input_string);
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        Main m = new Main();
        ArrayList<Integer> result = m.Josephus(n, k);
        System.out.print("<");
        for(int i : result) {
            System.out.print(i);
            if(i == result.get(result.size() - 1)) {
                break;
            }
            System.out.print(", ");
        }
        System.out.println(">");
    }
}

4.  접근

• 배열보다 ArrayList에서 제거 등의 작업이 용이하기 때문에 ArrayList를 이용합니다.
• k번째에 해당하는 사람이 순서대로 제거되므로 index로 변환하면 k - 1이 됩니다.
• 만약 N이 7, K가 3이라면, 제거되는 것을 생각하지 않고 index만 생각해본다면 2 -> 5 -> 1 -> 6 -> 4 -> 0 -> 3 순서이고, 제거되는 것을 생각하면서 index(size)로 보면 2(6) -> 4(5) -> 1(4) -> 3(3) -> 2(2) -> 0(1) -> 0(0) 순서인데, 현재ArrayList를 사용하여 제거하면서 진행할 예정이기 때문에 후자를 사용합니다.
• 규칙을 보면, 계속 k - 1에 해당하는 값을 ArrayList에서 제거하고 해당 index에 k - 1을 더하는데, 더한 값이 현재 ArrayList에 남아있는 최대 index를 넘어간다면, 한 바퀴를 돈 것이므로 ArrayList에 남아있는 개수만큼 빼준다면, 알맞는 index 번호가 나옵니다.