백준
[JAVA] 백준 11866번: 요세푸스 문제 0
스파게티 코더
2024. 7. 16. 16:35
문제
- 1번부터 N번까지 사람들이 원을 이루고 앉아있고 순서대로 K번째 사람을 제거하며 모든 사람이 제거될 때까지 반복할 때, 제거되는 순서(요세푸스 순열)를 출력하는 문제.
아이디어
- 큐를 이용해 문제 내용을 그대로 구현할 수 있다.
- 큐를 선언하고 1 ~ N 을 저장한다.
- 큐의 가장 첫번째 사람을 뒤로 옮기며 이 과정을 K-1번 반복한다.
- 반복 이후 큐의 가장 첫번째 사람이 우리가 제거해야 하는 K번째 사람이므로 제거하고 출력한다.
- 이 과정을 큐에 사람이 없을 때까지(큐가 빌 때까지) 반복한다.
풀이
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
// 큐 선언
Deque<Integer> deque = new ArrayDeque<>();
// 큐에 1 ~ N번째 사람 추가
for(int i=1; i<N+1; i++) {
deque.addLast(i);
}
sb.append('<');
while(true) {
// 큐의 가장 앞 사람을 큐의 맨 뒤로 옮김
for(int i=0; i<K-1; i++) {
deque.addLast(deque.removeFirst());
}
// K번째 사람 제거
sb.append(deque.removeFirst());
// 큐가 비었다면(모든 사람을 제거했다면) 탈출
if(deque.isEmpty()){
sb.append('>');
break;
}
sb.append(", ");
}
System.out.println(sb);
}
}
채점 결과
기타
- 큐를 이용해 문제를 그대로 구현하는 느낌이 재미있었다.