[백준] (Java) 요세푸스 문제 (큐)

 

📑 1. 문제설명

✅ 문제
 
이문제는 유대인 역사가 플라비우스 요세푸스가 만든 문제이다.
 
N명의 사람이 원 형태로 서 있다. 각 사람은 1부터 N까지 번호표를 갖고 있다. 그리고 임의의 숫자 K가 주어졌을 때 다음과 같이 사람을 없앤다.

• 1번 번호표를 가진 사람을 기준으로 K번째 사람을 없앤다.
• 없앤 사람 다음 사람을 기준으로 하고 다시 K번째 사람을 없앤다.

N과 K가 주어질 때 마지막에 살아 있는 사람의 번호를 반환하는 solution() 함수를 구현해주세요
 
✅ 제약조건

• N과 K는 1이상 1000이하의 자연수이다. 

 
✅ 입출력 예

N	K	return
5	2	3

 

💡 2. 풀이 과정

입출력 예를 그대로 그림으로 구현하려고 한다.

• N = 5, K = 2 이고 사람마다 1~5번까지의 숫자를 붙여 원형으로 배치한다.
• 그리고 첫번째 코드가 실행될 때의 기준은 1번이다.

주어진 예시에서 k = 2인데, k=2 라는 건 현재 위치에서 바로 다음 사람을 제거한다는 뜻이다. 

• k=2 일 때,  첫 번째 사람을 건너뛰고 두 번째 사람을 제거한다.
• 그 다음 차례는 제거된 사람의 다음 사람으로 기준이 넘어간다.
• 기준이 된 사람을 건너뛰고 옆 사람을 제거한다 (k = 2)
• 이 과정을 남은 사람이 한 명이 될 때까지 반복하면 된다.

즉, 매번 바로 옆에 있는 사람을 제거하는 것이기때문에 원 형태로 배열된 사람들이 한 칸씩 건너면서 사라지는 패턴을 가지게 된다. 

기준이 1번이기 때문에 K번째 사람은 2번 번호표를 가진 사람이다. 이 사람을 첫번째로 제거하고, 다음 위치를 3번으로 이동한다. 
 

기준이 3번이므로 3에서시작해서 2번째 사람인 4번을 제거한다. 그리고 새로운 기준은 5번이 된다.
 

5번을 기준으로 k = 2번째 사람인 1번을 제거하고 새로운 기준은 3번으로 넘어온다.
 

3번이 기준이므로 그 다음 사람인 5번을 제거한다.
 

가장 마지막으로 제거되는 사람은 3번이다.

---

⭐ 3. 정답코드

package algo03.StackAndQueue;

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

public class queue_josephus {

    public static void main(String[] args) {
        System.out.println(solution(5, 2)); // 결과: 3
    }

    /**
     * 요세푸스 문제를 해결하는 함수
     * 
     * @param N 사람의 수 (1부터 N까지 번호가 있음)
     * @param K 제거할 순번 (K번째 사람을 계속 제거함)
     * @return 마지막에 살아남은 사람의 번호
     */
    public static int solution(int N, int K) {
        // 큐(Queue) 생성: 원형 구조를 시뮬레이션하기 위해 사용
        Queue<Integer> queue = new LinkedList<>();

        // 1부터 N까지의 사람을 큐에 추가
        for (int i = 1; i <= N; i++) {
            queue.add(i);
        }

        // 마지막 한 명이 남을 때까지 반복
        while (queue.size() > 1) {
            // K번째 사람을 제거하기 위해 K-1번 앞의 사람을 뒤로 보냄
            for (int i = 1; i < K; i++) {
                queue.add(queue.poll()); // 맨 앞 사람을 빼서 큐의 뒤에 추가
            }
            queue.poll(); // K번째 사람 제거
        }

        // 마지막 남은 사람 반환
        return queue.poll();
    }
}

 
큐(Queue) 는 간단하게 말해서 FIFO (First In, First Out) 구조를 가진 자료 구조로 먼저 들어온 데이터가 먼저 나가는 방식이다. Java에서 LinkedList를 사용해 Queue를 구현 할 수 있다.

• poll() → 맨 앞 원소를 제거하고 반환하기
• add() → 큐의 뒤에 새로운 원소 추가하기

먼저 큐를 초기화하고, 1 ~ N까지 사람을 큐에 삽입한다. 그리고 나서 K번째 사람을 제거하는 과정은 아래와 같다.

• queue.add(queue.poll()); → K-1번 동안 맨 앞 사람을 빼서 뒤로 이동한다.
• queue.poll(); → K번째 사람을 제거한다.
• return queue.poll(); → 마지막 한 명이 남으면 반환한다. 

---

🐦 4. 같은 유형 문제

[프로그래머스] (Java) 카드뭉치 (큐)

[프로그래머스] (Java) 주식가격 (스택/큐)

[프로그래머스] (Java) 다리를 지나는 트럭 (스택/큐)

[프로그래머스] (Java) 프로세스 문제풀이 (스택/큐)

[프로그래머스] (Java) 기능개발 (스택/큐)