반응형
이번 글에서 백준 11866번 문제를 통해 요세푸스 순열을 활용,
이를 통해 원형 큐와 결합하여 사용해보자.
문제 핵심
- N : 사람 수
- K : 건너뛸 수
- ( 1 <= K <= N <= 1,000 )
풀이 과정
다음 문제는 요세푸스를 순열을 통해 한 사람씩 제거해 나가는 문제이다.
다음 글을 통해 개념을 참고하면 좋을 것 같다. 비교적 간단하다.
플라비우스 요세푸스 순열
요세푸스 순열은 유대인 역사가 플라비우스 요세푸스의 이야기에서 유래한 수학적 문제이다.요세푸스의 이야기1세기 로마 제국 시대, 유대인은 로마에 대항하여 대규모 반란을 일으켰다.이 때,
p-coding.tistory.com
1. 반복
해당 문제는 K의 배수마다 값을 꺼내오면 된다.
때문에 이전 값들은 모두 다시 큐의 뒤에 넣어주고 그 과정을 마지막 한 사람이 남을 때까지 반복해준다.
while(1 < queue.size()) {
count++;
if(count % K == 0){
stringBuilder.append(queue.remove() + ", ");
continue;
}
queue.add(queue.remove());
}2. 출력
백준의 문제 출력 조건에 따라 마지막 값은 기호와 함께 처리해 준다.
stringBuilder.append(queue.remove() + ">");
System.out.println(stringBuilder);
이번 문제는 큐의 개념과 요세푸스 순열을 이해하고 있다면,
결합하여 아주 쉽게 풀 수 있는 문제이다.
요세푸스 문제는 재귀로도 풀 수 있는 만큼 한 번 시도해보는 것도 좋다.
전체코드
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 {
Queue<Integer> queue = new LinkedList<Integer>();
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("<");
int N = Integer.parseInt(stringTokenizer.nextToken());
int K = Integer.parseInt(stringTokenizer.nextToken());
for(int i = 0; i < N; i++) {
queue.add(i + 1);
}
int count = 0;
while(1 < queue.size()) {
count++;
if(count % K == 0){
stringBuilder.append(queue.remove() + ", ");
continue;
}
queue.add(queue.remove());
}
stringBuilder.append(queue.remove() + ">");
System.out.println(stringBuilder);
}
}반응형
'백준 단계별 풀이' 카테고리의 다른 글
| [ 백준 2346번 문제 ] 풍선 터뜨리기 - JAVA (2) | 2025.03.02 |
|---|---|
| [ 백준 28279번 문제 ] 덱 2 - JAVA (1) | 2025.03.01 |
| [ 백준 2164번 문제 ] 카드2 (0) | 2025.02.27 |
| [ 백준 28278번 문제 ] 스택 2 - JAVA (1) | 2025.02.04 |
| [ 백준 17103번 문제 ] 골드바흐 파티션 - JAVA (0) | 2025.01.04 |
