문제
요세푸스 문제는 다음과 같다.
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 ≤ 5,000)
출력
예제와 같이 요세푸스 순열을 출력한다.
예제 입력 1
7 3
예제 출력 1
<3, 6, 2, 7, 5, 1, 4>
풀이
-
1부터 N까지 연결리스트에 넣는다.
-
현재 idx에서 k만큼 떨어진 인덱스에 해당하는 값을 결과 배열에 넣는다.
-
해당하는 idx의 숫자를 리스트에서 제거한다.
-
idx를 다음 인덱스로 바꾼다.
-
리스트가 비어있지 않을 때까지 진행한다.
-
마지막에 결과를 형식에 맞게 출력한다.
코드
연결리스트로 풀기
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
/*
date: 21.07.25 12:33 ~ 13:20
BOJ 1158
I: int N, int K
O: int 순열
C:
1 ~ N 번
1 <= K <= N <= 5,000
N명의 사람이 모두 제거될 때까지 K번째 사람을 제거
E:
k = n = 1 -> 1
=> n = 1 -> 1
n=7, k=3 -> 7명이 제거될 때까지 3번째 사람을 제거
3 6 2 7 5 1 4
배열 1 ~ n
지워진 자리 0
0이 아닐 때 횟수 카운팅 k번째
연결리스트
time: 리스트에 넣는 연산 -> O(N),
리스트에 넣는데, 항상 헤드부터 시작해서 해당 인덱스까지 타고 간다 -> O(N^2)
space: O(N)
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
// base case
if (n == 1) {
System.out.println("<1>");
return;
}
int[] result = new int[n];
int resultIdx = 0;
List<Integer> list = new LinkedList<>();
for (int i = 1; i <= n; i++) {
list.add(i);
}
int idx = 0;
while (list.size() > 0) {
int nextIdx = (idx + k - 1) % list.size();
int num = list.get(nextIdx);
if (list.size() == 1) {
result[resultIdx] = num;
} else {
result[resultIdx++] = num;
}
list.remove(nextIdx);
idx = nextIdx;
}
System.out.print("<");
System.out.print(result[0]);
for (int i = 1; i < result.length; i++) {
System.out.print(", " + result[i]);
}
System.out.print(">");
}
}큐로 풀기
1. 큐에 숫자를 다 넣은 뒤 순열 구하기
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
// base case
if (n == 1) {
System.out.println("<1>");
return;
}
int[] result = new int[n];
int resultIdx = 0;
Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i <= n; i++) {
queue.add(i);
}
while (queue.size() > 1) {
int curNum = 0;
for (int i = 0; i < k; i++) {
curNum = queue.poll();
if (i != k - 1) {
queue.add(curNum);
}
}
result[resultIdx++] = curNum;
}
result[resultIdx] = queue.poll();
System.out.print("<");
System.out.print(result[0]);
for (int i = 1; i < result.length; i++) {
System.out.print(", " + result[i]);
}
System.out.print(">");
}
}
2. 큐에 숫자를 넣으면서 순열 구하기
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
// base case
if (n == 1) {
System.out.println("<1>");
return;
}
int[] result = new int[n];
int resultIdx = 0;
int count = 0;
Queue<Integer> queue = new LinkedList<>();
int curNum = 1;
for (; curNum <= n; curNum++) {
if (curNum % k == 0) {
result[resultIdx++] = curNum;
count = 0;
} else {
queue.add(curNum);
count++;
}
}
while (queue.size() > 1) {
for (; count < k; count++) {
curNum = queue.poll();
if (count != k-1) {
queue.add(curNum);
}
}
count = 0;
result[resultIdx++] = curNum;
}
if (queue.size() == 1) {
result[resultIdx] = queue.poll();
}
System.out.print("<");
System.out.print(result[0]);
for (int i = 1; i < result.length; i++) {
System.out.print(", " + result[i]);
}
System.out.print(">");
}
}
차근차근 하나씩