[백준] 1158번 요세푸스 문제 (Java)

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

1158번: 요세푸스 문제

---

문제

---

알고리즘

 

이 문제는 Queue를 사용해서 문제를 해결하면 쉽다!

 

1. 1~N까지의 정수를 Queue에 add 해준다.

2. K-1번을 poll해서 다시 Queue에 add해준다.

3. 그러면 Queue의 맨 앞의 숫자를 poll 해서 삭제한다.

4. 1~3번을 Queue의 size가 1일 때까지 반복한다.

5. 마지막 Queue의 숫자를 빼서 해결 !

 

---

코드

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

public class Main {
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        Queue<Integer> que = new LinkedList<>();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        for(int i=1; i<=N; i++) {
            que.offer(i);
        }

        int cnt = 1;
        bw.write("<");
        while(que.size() != 1) {
            if(cnt == K) {
                bw.write(que.peek() + ", ");
                que.poll();
                cnt = 1;
            }
            else {
                que.offer(que.poll());
                cnt++;
            }
        }

        bw.write(que.poll() + ">");
        
        bw.flush();
        br.close();
        bw.close();
    }
}