요세푸스 문제

문제

요세푸스 문제는 다음과 같다.

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>

문제 풀이

import java.util.ArrayList;
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();
		int idx=K-1;
		ArrayList<Integer> arr=new ArrayList<>();
		
		LinkedList<Integer> list=new LinkedList<>();
		for(int i=1;i<N+1;i++) {
			list.add(i);
		}
		
		while(list.size()!=0) {
			arr.add(list.get(idx));
			list.remove(idx);
			idx=idx+K-1;
			if(list.size()!=0 && idx>=list.size()) {
				idx=idx%list.size();
			}
		}
		
		System.out.print("<");
		for(int i=0;i<arr.size();i++) {
			if(i==arr.size()-1) {
				System.out.print(arr.get(i)+">");
			}else {
				System.out.print(arr.get(i)+", ");
			}
		}
	}

}

자주 보이던 요세푸스 문제이다. 처음 읽으면 살짝 헷갈릴 수 있는 문제인데 문제를 읽어보고 잘 생각해보면 규칙을 찾을 수 있다.

우선, 1,2,3,4,5가 둥글게 앉아있다고 했을때, 2번째 사람을 뺀다고 생각해보자.

처음에는 2번이 빠지게되고 1,3,4,5가 남게된다. 이때, 다시 처음부터 2번째 사람이 빠지게 되는 구조가 아니라 2번이 있었던 자리에서부터 2번째 사람을 빼야한다.

그렇다면 다음엔 4번이 빠지게 될 것이다. 즉, 인덱스의 값을 꾸준하게 2 크기만큼 키워야하는데, 또 한번 생각해야할 것은 숫자 하나가 빠지게 되기 때문에 정확하게는 2크기가 아니라 2-1크기를 키워야한다.

idx=idx+2-1

라고 생각하면 된다.

그리고 배열의 크기를 넘기게 되면 오류가 발생하기 때문에 if문으로 조건을 걸어주어 인덱스가 배열의 크기를 넘어가게 되면 %을 이용하여 현재 배열의 크기의 나머지를 인덱스로 해주면 된다.

본인은 일일이 인덱스를 구해주면서 문제를 풀려고 했다면 다른 풀이로는 큐를 이용하는 방법이 있다.

큐 이용한 풀이

배열의 값을 하나씩 offer한 후 첫번째 값을 뒤로 보낸다.

이때, K값이 나오게되면 poll하여 값을 출력한다.

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);
		StringBuilder sb=new StringBuilder();
		
		int N=sc.nextInt();
		int K=sc.nextInt();
		
		Queue<Integer> queue=new LinkedList<>();
		
		for(int i=0;i<N;i++) {
			queue.offer(i+1);
		}
		
		int idx=1;
		sb.append("<");
		while(queue.size()>1) {
			int num=queue.poll();
			if(idx==K) {
				sb.append(num+", ");
				idx=0;
			}else {
				queue.offer(num);
			}
			idx++;
		}
		sb.append(queue.peek()+">");
        
        System.out.println(sb);
	}

}

이렇게 풀 수도 있다.