백준1158 : 요세푸스 문제 - JAVA

요세푸스 문제 0 분류

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

512 MB

18618

10643

9197

58.095%

문제

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

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)

출력

예제와 같이 요세푸스 순열을 출력한다.

예제 입력 1 복사

7 3

예제 출력 1 복사

<3, 6, 2, 7, 5, 1, 4>

 

 

---

오세푸스 순열 또는 오세푸스 문제는 다음과 같이 정의 할 수 있다. 

 

전산학이나 수학에서 요세푸스 문제(Josephus problem) 혹은 요세푸스 순열(Josephus permutation)은 다음과 같이 정의한다.

n과 k가 자연수이고, k < n이라고 가정한다. n명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 k번째 사람을 모임에서 제외한다. 남은 n-1명에서 다시 다음 사람부터 순서를 세서 k번째 사람을 모임에서 제외한다. 이것을 아무도 남지 않을 때까지 계속해서 반복한다. 이때 모임에서 제외되는 사람의 순서를 (n, k) 요세푸스 순열이라고 하며 마지막으로 제외되는 사람을 구하는 문제를 요세푸스 문제라고 한다.

예를 들어 (7,3) 요세푸스 순열은 {3,6,2,7,5,1,4}이며 4번째 위치한 사람이 마지막으로 제외되게 된다.

 

---

 

import java.util.Scanner;
import java.util.LinkedList;

public class Main {

	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		LinkedList<Integer> list = new LinkedList<Integer>();
		
		int N = scan.nextInt();
		int K = scan.nextInt();
		
		for(int i = 1; i <= N; i++) {
			list.add(i);
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append("<");
		
		int index = 0; // 리스트의 첫 index는 0부터! 들어가는 숫자는 1들어가있음
		
		while(list.size() > 1) {
			index = (index + (K - 1)) % list.size();
			
			sb.append(list.remove(index)).append(", ");
		}
		
		sb.append(list.remove()).append(">");
		System.out.println(sb);
		
		scan.close();
	}
}

StringBuilder를 앞으로 많이 사용해야겠다.

index값에는 0부터 들어가고 k는 1번부터 세는거기 때문에 k-1을 더해줘야했다. 

그리고 원으로 생각하기 때문에, index + ( k - 1)이 원의 list.size보다 커지는 경우가 오기 때문에 list.size로 나눠줘야한다! - 거의 모든 원문제는 다 원의 size로 나누는 듯 하다 

---

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner scan = new Scanner(System.in);
		Queue<Integer> queue = new LinkedList<>();
		
		int N = scan.nextInt();
		int K = scan.nextInt();
		
		for(int i = 1; i <= N; i++) {
			queue.add(i);
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append("<");
		
		while(queue.size() > 1) {
			
			for(int i = 1; i < K; i++) {
				int value = queue.poll();
				queue.add(value);
			}
			sb.append(queue.poll()).append(", ");
		}
		sb.append(queue.poll()).append(">");
		System.out.println(sb);
		scan.close();
	}
}

Queue를 이용해서 푸는 방법 

그 앞 숫자를 삭제하고 뒤에 다시 삽입하는 과정을 통해서 linkedList를 재구성하고 3번째 index를 계속 반복해서 삭제한다.

삭제와 삽입이 많이 있어서 그런지 시간이 더 걸림