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 ≤ 5,000)
출력
예제와 같이 요세푸스 순열을 출력한다.
풀이 1
링크드 리스트를 큐처럼 활용하여 풀었다.
cnt는 1부터 시작해서 K일 경우에만 제거하고, 아닌 경우에는 리스트에 마지막에 다시 붙여준다.
이 과정을 반복하여 list의 크기가 0이 되면 값을 반환한다.
import java.util.LinkedList;
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();
LinkedList<Integer> list = new LinkedList<>();
for (int i = 1; i <= N; i++) {
list.add(i);
}
StringBuilder sb = new StringBuilder();
sb.append("<");
int cnt = 1;
while (list.size() > 0) {
if (cnt != K) { // 제거x
list.add(list.remove(0)); // 뒤에 붙여줌
cnt++;
} else { // K번째
if (list.size() == 1) {
sb.append(list.remove(0) + ">");
} else {
sb.append(list.remove(0) + ", ");
cnt = 1;
}
}
}
System.out.println(sb.toString());
}
}
풀이 2
순환하는 index를 나머지 연산자를 이용하여 풀었다.
cnt는 제거할 index이고, cnt에 K-1을 더하며 list의 크기만큼 나머지를 구하면 해당 index가 된다.
while (list.size() > 0) {
cnt = (cnt + K - 1) % list.size();
if (list.size() == 1) {
sb.append(list.remove(cnt) + ">");
} else
sb.append(list.remove(cnt) + ", ");
}
728x90
'문제 풀이 > BOJ' 카테고리의 다른 글
[백준] 2559 - 수열 (자바/Java) (0) | 2022.08.18 |
---|---|
[백준] 2304 - 창고 다각형 (자바/Java) (0) | 2022.08.18 |
[백준] 4949 - 균형잡힌 세상 (자바/Java) 스택 Stack (0) | 2022.08.16 |
[백준] 9012 - 괄호 (자바/Java) 스택 Stack 괄호 검사 (0) | 2022.08.16 |
[백준] 10156 - 개미 (자바/Java) (0) | 2022.08.15 |