[BOJ] 11866 - 요세푸스 문제 0 (Java)

알고리즘

• 구현
• 자료 구조
• 큐

1. 문제

요세푸스 문제

N명의 사람이 원형으로 앉아있을 때, 주어진 규칙에 따라 K번째 사람을 계속해서 제거해가는 문제

2. Idea

• LinkedList Class를 이용한 Queue를 사용하는 것이 핵심
• 큐의 선입선출(FIFO) 특성 사용
• LinkedList 사용 이유: 사람들이 원형으로 앉아있고, K번째로 나오는 사람을 제거하는 방식
  -> K번째로 나오는 사람을 뽑아내고 다시 뒤로 보내는 작업을 효율적으로 하기 위함

Queue의 메소드

1. boolean add(E e) 또는 boolean offer(E e)

• 큐에 원소를 추가
• add: 큐에 새로운 원소를 추가하며, 큐에 공간이 부족하면 예외를 발생시킵니다.
• offer: 큐에 새로운 원소를 추가하며, 큐에 공간이 부족하면 false를 반환합니다.

2. E remove() 또는 E poll()

• 큐에서 맨 앞의 원소를 제거하고 반환합니다.

3. remove

• 큐에서 원소를 제거하며, 큐가 비어있으면 예외를 발생시킵니다.

4. poll

• 큐에서 원소를 제거하며, 큐가 비어있으면 null을 반환합니다.

5. E element() 또는 E peek()

• 큐의 맨 앞에 있는 원소를 반환합니다.

6. element

• 큐의 맨 앞에 있는 원소를 반환, 큐가 비어있으면 예외 발생

7. peek

• 큐의 맨 앞에 있는 원소 반환, 큐가 비어있으면 null 반환

8. boolean isEmpty()

• 큐가 비어있는지 여부를 반환

9. int size()

• 큐에 저장된 원소의 개수를 반환

3. 풀이

3.1. 변수 입력 및 큐 생성

• N: 사람 수
• K:K번째 사람 제거
• LinkedList Queue 생성

Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
Queue<Integer> q = new LinkedList<>();  // 큐를 LinkedList로 초기화

for (int i = 1; i <= N; i++) { q.add(i); } //큐 생성

3.2. 요세푸스 문제 해결

• 큐가 빌 때까지 반복
• 매번 K-1번째 원소를 큐에서 빼서 다시 뒤로 넣어줍니다.
• K번째 원소를 출력하면서 큐에서 제거
• 큐가 비어있지 않으면 ,와 공백을 출력하여 구분

while (!q.isEmpty()) {
	for (int i = 0; i < K - 1; i++) { // K-1번 앞에 있는 원소를 뒤로 보냄
		int val = q.poll();
		q.offer(val);
    }
	// K번째로 나오는 원소를 삭제함과 동시에 출력
	System.out.print(q.poll());
	// 큐가 비어있지 않으면 쉼표와 공백 추가
	if (!q.isEmpty()) { System.out.print(", "); }
}

3.3. 결과 출력

• 조건에 맞게 출력
  예시: <3, 6, 2, 7, 5, 1, 4>

System.out.print("<");
...
System.out.println(">");

4. 전체코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        Queue<Integer> q = new LinkedList<>();  // 큐를 LinkedList로 초기화

        for (int i = 1; i <= N; i++) { q.add(i); } //큐 생성

        System.out.print("<");

        while (!q.isEmpty()) {
            for (int i = 0; i < K - 1; i++) { // K-1번 앞에 있는 원소를 뒤로 보냄
                int val = q.poll();
                q.offer(val);
            }
            // K번째로 나오는 원소를 삭제함과 동시에 출력
            System.out.print(q.poll());
            // 큐가 비어있지 않으면 쉼표와 공백 추가
            if (!q.isEmpty()) { System.out.print(", "); }
        }
        System.out.println(">");
    }
}