[JOSEPHUS] 조세푸스 문제
개발이야기/알고스팟2022. 1. 9. 18:37
Java 로 풀어보는 알고리즘입니다. 📖
코딩테스트를 대비하여 JAVA1.8 부터 제공되는 함수형 API 는 사용하지 않았습니다.
문제 : https://algospot.com/judge/problem/read/JOSEPHUS
algospot.com :: JOSEPHUS
조세푸스 문제 문제 정보 문제 1세기에 살던 역사학자 조세푸스는 로마와의 전쟁에서 패해 N - 1명의 동료 병사들과 함께 출구가 없는 동굴에 포위당했다고 합니다. 동료 병사들은 로마에 항복하
algospot.com
풀이입니다. 🤔
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
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));
}
}
}
|
cs |
Queue 를 이용하면 문제를 쉽게 해결할 수 있습니다.
최종 2명이 남을 때까지 Queue 에서 1회 선출, k-1 회 선출 후 재입력을 하게 되면 마지막까지 생존한 2명을 구할 수 있습니다.
이 포스트를 읽어주셔서 감사합니다. 🙇🏻♂️
반응형
'개발이야기 > 알고스팟' 카테고리의 다른 글
| [FENCE] 울타리 잘라내기 (0) | 2022.01.14 |
|---|---|
| [QUADTREE] 쿼드 트리 뒤집기 (0) | 2022.01.14 |
| [CCR] 문자 인식 (0) | 2022.01.09 |
| [SPETIAL] Spatial Concepts Test (0) | 2022.01.09 |
| [WORDLENGTH] 단어 길이 재기 (0) | 2022.01.07 |