[JOSEPHUS] 조세푸스 문제

Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.

문제 : https://algospot.com/judge/problem/read/JOSEPHUS

algospot.com :: JOSEPHUS

 

풀이입니다. 🤔

 

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Queue<Integer> queue = new ArrayDeque<>();
        int cases = scanner.nextInt();
        while (cases-- > 0) {
            int n = scanner.nextInt(), k = scanner.nextInt();
            for (int i = 1; i <= n; ++i) queue.offer(i);
            while (queue.size() > 2) {
                queue.poll();
                for (int i = 0, len = k - 1; i < len; ++i) queue.offer(queue.poll());
            }
 
            int first = queue.poll(), second = queue.poll();
            System.out.printf("%d %d\n", Math.min(first, second), Math.max(first, second));
        }
    }
}

 

Queue 를 이용하면 문제를 쉽게 해결할 수 있습니다.

최종 2명이 남을 때까지 Queue 에서 1회 선출, k-1 회 선출 후 재입력을 하게 되면 마지막까지 생존한 2명을 구할 수 있습니다. 

 

 

 

이 포스트를 읽어주셔서 감사합니다. 🙇🏻‍♂️