[백준 / Java] 1158. 요세푸스 문제

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

 

---

💻 풀이 결과

 

💯 최종 코드

import java.util.LinkedList;
import java.util.List;
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();

		List<Integer> list = new LinkedList<>();
		for (int i = 1; i <= N; i++) {
			list.add(i);
		}

		sb.append("<");

		int idx = 0;
		int cnt = 0;
		while (true) {
			cnt++;

			if (list.size() == 1) {
				sb.append(list.remove(idx)).append(">");
				break;
			}

			if (cnt == K) {
				sb.append(list.remove(idx)).append(", ");
				cnt = 0;
			} else {
				idx++;
			}

			if (idx >= list.size()) {
				idx = 0;
			}
		}

		System.out.println(sb);
	}
}

 

💬 풀이 과정

• 컴파일 에러는 클래스명 오류ㅠㅠ
• 예전에 풀었을 때는 큐를 사용하였고, 다시 풀었을 때는 리스트를 사용하였다.

예전 풀이 과정

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);
		
		Queue<Integer> josephus = new LinkedList<>();
		
		// 총 인원 수
		int N = sc.nextInt();
		// K 번째 사람 제거
		int K = sc.nextInt();
		// 제거된 사람을 차례대로 집어넣을 배열
		int[] arr = new int[N];
		
		// 1번부터 N번까지 사람들에게 차례대로 번호를 부여
		for(int i = 1; i <= N; i++) {
			josephus.add(i);
		}
		
		// 다 제거할 때까지 반복문 돌리기
		for(int i = 0; i < N; i++) {
			// K 번째에 제거를 해야하는데, 그 K 번째를 세기 위해서 카운팅
			int cnt = 1;
			
			// K 번째 전까지 살려두는 사람을 뒤로 보낸다
			while(cnt < K) {
				josephus.add(josephus.poll());
				cnt++;
			}
			
			// K 번째에서 제거하고 제거된 사람배열에 집어넣는다
			arr[i] = josephus.poll();
		}
		
		// 출력
		System.out.print("<");
		for(int i = 0; i < (N - 1); i++) {
			System.out.print(arr[i] + ", ");
		}
		System.out.print(arr[N-1] + ">");
	}
}

💡 깨달은 점

1. 요세푸스 문제? 요세푸스 순열?

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

2. 리스트를 활용한 풀이

• 카운팅이 k 가 될 때까지를 반복하면서 리스트의 인덱스를 조정한다.
• 리스트의 idx 도 끝까지 갔을 때 다시 처음으로 가도록 설정한다.
• 리스트의 크기가 1이 될 때까지 반복한다.
• 큐를 사용했을 때보다 시간 복잡도가 훨씬 작아졌다.