[Baekjoon/Java] 요세푸스 문제

문제

 

1158번: 요세푸스 문제

풀이

위처럼 앞에서 K-1개 만큼을 맨 뒤로 보낸 뒤 맨 앞에 있는 값을 뽑아주면 된다.

import java.util.LinkedList;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int K = scanner.nextInt();
        LinkedList<Integer> people = new LinkedList<>(IntStream.rangeClosed(1, N).boxed().collect(Collectors.toList()));
        String[] removedPeople = new String[N];
        int cnt = 0;
        while (!people.isEmpty()) {
            for (int i=0; i<K-1; i++) {
                people.add(people.pollFirst());
            }
            removedPeople[cnt++] = String.valueOf(people.pollFirst());
        }
        System.out.println("<" + String.join(", ", removedPeople) + ">");
    }
}

•  LinkedList를 활용한 문제
• 시간복잡도: O(n)