[백준]1158번 : 요세푸스 문제

문제

---

해결방법

---

여러 해결 방법이 있지만 요세푸스 문제의 대표적인 해결 방법인 Queue 자료구조를 이용하여 접근을 하였다.

1. 1 - N 번까지의 사람을 먼저 Queue에 순차적으로 넣어준다.
2. Queue에서 다 뽑을 때까지 계속 반복문을 돌린다 while 이용
3. K의 배수가 아닌 값은 Queue에서 뽑은 후에 다시 Queue에 넣는다.
4. 뽑은 값은 StringBuilder에 추가를 해준다.
5. 최종적으로 StringBulder를 출력을 해준다.

 

작성코드

---

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        //queue를 선언한다.
        Queue<Integer> queue = new LinkedList<>();

        int N = scanner.nextInt();
        int K = scanner.nextInt();

        //1 ~ N번까지 queue에 추가.
        for(int i =1;i<=N;i++) {
            queue.add(i);
        }

        //String을 계속 추가, 수정해야하므로 StringBuilder 선언 !
        StringBuilder people = new StringBuilder();
        people.append('<');

        //queue에서 사람을 다 뽑을 때까지 돌린다.
        while (queue.size()>1) {

            //K의 배수가 아닌 값은 뽑고 다시 넣는다.
            for(int i =0; i<K-1;i++) {
                int val = queue.poll();
                queue.offer(val);
            }
            //뽑은 값을 String에 추가
            people.append(queue.poll()).append(", ");
        }

        //마지막에 '>'로 닫아주고 출력
        people.append(queue.poll()).append('>');
        System.out.println(people);
    }
}