문제
요세푸스 문제는 다음과 같다.
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)
출력
예제와 같이 요세푸스 순열을 출력한다.
출처
- 문제를 만든 사람: baekjoon
요세푸스 순열이라는 것이 정말 있는 순열인지 궁금해지는 문제입니다.
그래서 위키백과에 검색해보니 정말로 있는 순열 문제였습니다.
시간 복잡도가 O(n)이라고 알려져 있는 유명한 알고리즘인 것 같습니다.
이러한 원판이 있고 하나씩 제거해 나가는 알고리즘에 대한 문제입니다.
문제에서 말하고 있듯, 선입 선출에 해당하는 큐 자료구조를 이용해야 합니다.
모든 분들이 잘 알고있듯이 큐는 삽입한 순서 혹은 입력된 순서대로 원소가 나열되며
가장 먼저 입려된 원소가 맨 앞에 있다가 가장 먼저 삭제가되는 자료구조입니다.
일단 저는 이 알고리즘 문제를 풀면서 한번에 맞은 것 같네요
import java.util.Scanner;
import java.util.Vector;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int t = m;
Vector<Integer> a = new Vector<Integer>(n);
for (int i = 0; i < n; i++) {
a.add(i + 1);
}
System.out.print("<");
while (a.size() > 1) {
m -= 1;
System.out.print(a.get(m) + ", ");
a.remove(m);
for (int i = 0; i < t; i++) {
m++;
if (m > a.size()) {
m = 1;
}
}
}
System.out.println(a.get(0) + ">");
}
}코드 역시 굉장히 간단한 것으로 보입니다.
java를 이용해서 vector 자료구조를 이용해 간단한 큐 구조를 이루었고 이에 대한 알고리즘을 구현하였습니다.
코딩 테스트에서는 이처럼 처음 보는 수학적 용어를 사용하는 경우가 있습니다.
이 경우 대개 내용은 간단합니다. 오히려 당황하지 않고 평정심을 가지고 문제 풀이를 해나가는 것이
좋은 접근 방식입니다.
이상 다이어릿이었습니다. 감사합니다.
