백준 1158 - 요세푸스 문제

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

문제 풀이

해당 문제에서는 두가지 입력 N, K가 주어진다.

• N : 사람 수
• K : 원에서 사람이 제거되는 간격

N, K의 최대 5000 이므로, 최대 O(N^2)의 시간복잡도내에서 문제를 해결해야 한다.

전체 소스 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arguments = br.readLine().split(" ");

        int N, K;
        N = Integer.parseInt(arguments[0]);
        K = Integer.parseInt(arguments[1]);

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            list.add(i + 1);
        }

        int index = 0;
        StringBuilder sb = new StringBuilder();
        sb.append("<");

        // 사람을 간격에 맞게 하나씩 제거해준다.
        while (list.size() > 1) {
            index += K - 1;
            index %= list.size();
            int removedValue = list.remove(index);
            sb.append(Integer.toString(removedValue));
            sb.append(", ");
        }

        // 마지막 숫자를 제거한다.
        index += K - 1;
        index %= list.size();
        int removedValue = list.remove(index);
        sb.append(Integer.toString(removedValue));
        sb.append(">");

        System.out.println(sb.toString());

        br.close();
    }
}