[백준] 요세푸스 문제 0 (JAVA)

11866번: 요세푸스 문제 0

문제

---

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

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)

출력

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

 

예제 입력

7 3 // 7: N(사람 수), 3: K(제거할 순서)

예제 출력

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

 

 

K=3이므로 3번째 사람 제거 → 3번째 사람에서부터 그다음 3번째에 있는 사람인 6 제거 → 6에서 3번째에 있는 사람인 2 제거 → 2에서 3번째에 있는 사람인 7 제거 (이미 제거된 사람을 건너뛰고 순서를 센다.) → … 반복

 

 

문제 정리

---

전체 인원(N)과 양의 정수(K)가 주어지면 한 사람만 남을 때까지 사람들을 원에서 제거하는 순서 구하는 문제

 

입력

공백으로 구분된 두 개의 정수

• N : 첫 번째 정수, 총 인원
• K : 두 번째 정수, 양의 정수, 제거할 순서

출력

<> 안에 쉼표로 구분된 일련의 숫자로 요세푸스 순열 인쇄

 

요구 사항

• 입력 정수 N 및 K 읽기
• 1에서 N까지 레이블이 지정된 N개의 노드가 있는 순환 연결 목록 만들기
• 목록을 반복하고 하나의 노드만 남을 때까지 모든 K번째 노드 제거
• 노드가 제거된 순서대로 출력

 

 

해결 방법

---

1. 입력에서 N과 K 읽기
2. 1부터 N까지 레이블이 지정된 N개의 노드로 순환 링크 리스트 초기화
3. 현재 노드를 노드 1로 설정
4. While 목록에 노드가 두 개 이상 있는 동안: a. 목록을 반복하여 K번째 노드를 찾는다. b. K번째 노드 제거 c. 현재 노드를 제거한 노드를 바로 다음 노드로 설정
5. print 제거된 순서대로 노드 순서 출력

→ ArrayList를 이용하여 원형 리스트를 구현

 

코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
				// N 및 K에 대한 입력 값 읽기
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 인원 수
        int k = sc.nextInt(); // 제거될 사람의 번호

				// 원 안에 있는 사람들을 나타내는 정수 목록 초기화
        ArrayList<Integer> list = new ArrayList<>(); // 리스트 생성
        for (int i = 1; i <= n; i++) {
            list.add(i); // 리스트에 인원 추가
        }
				
				// 출력할 때 < 필요
        StringBuilder sb = new StringBuilder();
        sb.append("<");

				// 원의 시작 위치를 나타내는 변수 '인덱스'를 0으로 설정
        int idx = 0; // 루프 안에서는 이전에 마지막으로 제거된 사람의 인덱스를 나타냄

				// 사람 목록이 비워질 때까지 반
        while (list.size() > 1) { // 리스트의 크기가 1보다 큰 동안 반복
            **idx = (idx + k - 1) % list.size();** // K를 기준으로 제거될 사람의 인덱스 계산
            sb.append(list.remove(idx)).append(", "); // 해당 인덱스의 사람을 제거하고 출력 문자열에 추가
        }
        sb.append(list.get(0)).append(">"); // 마지막으로 남은 사람을 출력 문자열에 추가
        System.out.println(sb); // 결과 출력
    }
}

• idx = (idx + k - 1) % list.size() : 제거될 사람의 인덱스 계산
  • idx : 루프 안에서는 이전에 마지막으로 제거된 사람의 인덱스를 나타냄
  • k : 누구를 제거하기 전에 건너뛸 사람의 수
  • 제거할 다음 사람을 찾으려면 k 사람을 건너뛰어야 하므로 현재 인덱스 idx에 k-1을 추가하지만 이미 idx번째 사람에서 시작하고 있다.