[1158] 요세푸스 문제 in Java

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

1158번: 요세푸스 문제

---

접근 방식

: 원형이라는 단어를 보고 큐를 떠올렸음.

그래서 k번째에 있는 사람이 나오기 전까지 앞에 있는 사람을 poll()해서

offer()로 뒤에 다시 넣어주는 작업을 진행하면 되었던 문제

 

 

시행 착오

: 나온 결과값을 따로 answer이라는 배열에 넣어주려고 했다.

그런데, 그냥 StringBuilder를 이용해서 sb에 append해주면

굳이 배열을 이용할 필요가 없다는 걸 깨닫게 된 문제!

 

BufferWriter를 사용하려고 했는데 

StringBuilder가 성능이 더 빠르다고 하여

앞으로는 StringBuilder를 사용해볼 예정

 

package day_0808;
 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class n1158 {
    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()); // 사람 수 : n명 
        int k=Integer.parseInt(st.nextToken()); // k번째 사람 제거
        Queue<Integer> queue= new ArrayDeque<>(); // 큐 
        
        StringBuilder sb = new StringBuilder();
        sb.append("<");
        
        for(int i=1; i<=n; i++) {
            queue.add(i); // 큐에 순서대로 사람 넣기
        }
        while (queue.size()>1) {
            for(int i=0; i<k-1; i++) {
                queue.offer(queue.poll()); // k-1번째까지 사람들은 뽑아서 뒤로 보낸다.
            }
            sb.append(queue.poll() + ", "); // k번째 사람을 뽑아서 출력한다.
        }
        sb.append(queue.poll()+">"); // 마지막으로 남은 최후의 1인은 마지막에 따로 출력해준다.
        System.out.println(sb);
    }
}