728x90
실버
문제
요세푸스 문제는 다음과 같다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)
출력
예제와 같이 요세푸스 순열을 출력한다.
728x90
1. 원형 큐(링 버퍼)를 사용
- 먼저 1부터 N까지의 사람을 큐에 추가하여 초기화한다.
- K번째 요소의 앞에 있는 모든 요소 즉 K-1개의 요소를 큐의 끝으로 이동시킨다.
- K번째 요소를 큐에서 제거한다.
- 큐가 빌 때까지 반복한다.
큐 | 출력 |
1 2 3 4 5 6 7 | |
4 5 6 7 1 2 | 3 |
7 1 2 4 5 | 3 6 |
4 5 7 1 | 3 6 2 |
1 4 5 | 3 6 2 7 |
1 4 | 3 6 2 7 5 |
4 | 3 6 2 7 5 1 |
3 6 2 7 5 1 4 |
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));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= N; i++)
q.add(i);
StringBuilder sb = new StringBuilder();
sb.append('<');
while (!q.isEmpty()) {
for (int i = 0; i < K - 1; i++) {
q.add(q.remove());
}
sb.append(q.remove());
if (!q.isEmpty()) {
sb.append(", ");
}
}
sb.append('>');
bw.write(sb.toString());
bw.flush();
br.close();
bw.close();
}
}
2. 리스트 사용
- 1부터 N까지의 사람을 리스트에 저장한다.
- 현재 제거할 사람의 인덱스 변수를 생성한다(index). 사람 N은 인덱스 N-1에 위치하기 때문에 초기값은 K-1로 설정한다.
- index위치의 사람을 제거하고 다음 제거할 위치를 결정하기 위해 index에 K-1을 더한다.
- index가 리스트의 크기보다 클 경우 index를 리스트의 크기만큼 나눈 나머지를 index로 설정한다.
- 리스트가 빌 때까지 반복한다.
index | list | 출력 |
1 2 3 4 5 6 7 | ||
2 | 1 2 |
3 |
4 | 1 2 4 5 |
3 6 |
1 |
3 6 2 | |
3 | 1 4 5 |
3 6 2 7 |
1 4 |
3 6 2 7 5 | |
3 6 2 7 5 1 | ||
3 6 2 7 5 1 4 |
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));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
List<Integer> list = new ArrayList<>();
for (int i = 1; i <= N; i++)
list.add(i);
StringBuilder sb = new StringBuilder();
sb.append('<');
int index = K - 1;
while (!list.isEmpty()) {
if (index >= list.size())
index %= list.size();
sb.append(list.remove(index));
if (!list.isEmpty()) {
sb.append(", ");
}
index += (K - 1);
}
sb.append('>');
bw.write(sb.toString());
bw.flush();
br.close();
bw.close();
}
}
728x90
'백준 > Java' 카테고리의 다른 글
[백준 자바] 2161번(카드 1) - 큐 (0) | 2024.07.02 |
---|---|
[백준 자바] 10845번(큐) - Deque (0) | 2024.07.01 |
[백준 자바] 그대로 출력하기 1~2 - EOF (0) | 2024.07.01 |
[백준 자바] 25497번(기술 연계마스터 임스) (1) | 2024.06.28 |
[백준 자바] 10799번(쇠막대기) (0) | 2024.06.28 |