백준 1158번 ) 요세푸스 문제 (java)

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

1158번: 요세푸스 문제

 

문제

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
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(), " ");
        StringBuilder sb = new StringBuilder();

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

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

        for(int i=1; i<=N; i++){
            q.add(i);
        }
        sb.append("<");
        
        while(q.size() != 1){
            for(int i=0; i<K-1; i++){
                q.add(q.poll());
            }
            sb.append(q.poll() + ", ");
        }

        sb.append(q.poll() + ">");

        System.out.println(sb);

    }
}

예전에 학교 컴퓨터 알고리즘 수업 과제로 풀었던 케이크 문제와 비슷한 유형의 문제.

큐를 사용해서 순서대로 집어넣고, 해당하는 숫자가 아니면 다시 빼냈다가 집어넣고, 해당하는 순서의 숫자이면 빼내서 출력하는 방식으로 풀이.

 

주의할 점

• 항상 헷갈리는거지만 Queue<Integer> = new LinkedList<>();
• add, offer 와 poll, peek 구분하기!