[JAVA] 백준 1158번- 요세푸스 문제

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

1158번: 요세푸스 문제

 

import java.util.*;


public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        int k=sc.nextInt();

        Queue<Integer> Q = new LinkedList<>();
        StringBuilder sb = new StringBuilder();

        for(int i=1; i<=n; i++) Q.offer(i);
        sb.append('<');

        while(Q.size()!=1){
            for(int i=1; i<k; i++) Q.offer(Q.poll());
            sb.append(Q.poll()).append(", ");
        }
        sb.append(Q.poll()).append('>');
        System.out.println(sb);
    }
}

 

1부터 n까지의 숫자를 큐에 넣은 후,

큐의 첫번째 원소부터 k-1번째 숫자를 큐에서 빼고 맨 뒤에 추가한다.

k번째인 원소는 아예 큐에서 제거해버린다.

이렇게 큐에 남아있는 원소가 1이 아닐때까지 반복하고, 큐에 남아있는 마지막 원소는 그냥 poll하기만 하면 된다.