솜이의 데브로그

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

Algorithm/백준

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

somsoming 2022. 3. 15. 00:01

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

 

1158번: 요세푸스 문제

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

www.acmicpc.net

 

문제

 

풀이

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 구분하기!