백준 1158번 : 요세푸스 문제 java

이 문제는 자료 구조의 일종인 큐를 이용해서 요세푸스 순열을 구하는 문제입니다.

요세푸스 순열이란 K번째 사람을 제거해주면서 제거된 순서대로 출력하는 문제입니다.

이를 표로 조금 더 이해하기 쉽게 나타내겠습니다.

위 표를 보시면 어떤 순서로 사람이 제거되고 제거된 다음에는 배열이 어떻게 남아 있는지를 확인하실 수 있습니다.

저는 이 문제를 해결하기 위해서 큐를 사용하였습니다.

우선 큐에 사람들을 순서대로 넣습니다.

그리고 K번 만큼 뒷사람을 찾아갑니다.

뒷사람을 찾아가면서 지나친 사람들은 pop한 후 다시 offer해서 맨 뒤로 보내줍니다.

찾아간 인덱스에 있는 사람을 pop해서 answer배열에 넣습니다.

이 과정은 N번 반복하면 위의 Output처럼 결과가 나옵니다.

이를 코드로 보여드리겠습니다.

---

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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        Queue<Integer> q = new LinkedList<>();
        List<Integer> answer = new ArrayList<>();

        for(int i = 1; i<=N; i++)
            q.offer(i);

        while(!q.isEmpty()){
            for(int i = 0; i<K; i++){
                if(i == K-1)
                    answer.add(q.poll());
                else
                    q.offer(q.poll());
            }
        }

        System.out.print("<");
        for(int i = 0; i<N-1; i++)
            System.out.print(answer.remove(0)+", ");
        System.out.print(answer.remove(0)+">");
    }
}