[백준][Java] 11866번 요세푸스 문제 0

안녕하세요 :)

적어도 하루 1개 이상 알고리즘 문제를 해결하려 노력하고 있습니다.

혼자 해결 가능한 문제도 있고, 어려웠던 문제도 있던 차라 복습하고자  글을 써 내려갑니다.

 

---

 

백준 11866 요세푸스 문제 0

이 문제는 요세푸스 문제의 변형으로, 사람들 중에서 한 명씩 차례대로 제거해나가는 방식입니다.

덱을 사용하여 문제 풀이를 했고, 덱에 대한 자세한 설명은 하단 링크를 확인바랍니다.

[Algorithms] 자료구조 - 스택(Stack), 큐(Queue), 덱(Deque)

 

📘 문제

 

💡 해결 방법

Deque를 사용하여 양쪽 끝에서 효율적으로 데이터를 처리합니다.

사람들은 1부터 n까지 덱에 넣고, 차례로 첫 번째 사람을 빼고 그다음 사람을 뒤로 넣는 방식으로 해결합니다.

반복문을 통해 덱에서 하나씩 제거하는 작업을 하되, 마지막 남은 사람만 남을 때까지 계속해서 이 작업을 진행합니다.

 

✅ 풀이 및 설명 (설명은 더보기 클릭)

 

• Deque를 사용하여 양쪽 끝에서 카드를 빼고, 덱의 뒷부분에 사람을 넣는 방식으로 진행합니다.
• **pollFirst()**로 첫 번째 사람을 제거하고, 그다음 사람을 **offerLast()**로 뒤에 추가하는 방식으로 동작합니다.
• 반복문을 통해 덱에 사람이 하나만 남을 때까지 이 작업을 계속합니다.

 

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        
        // 1부터 n까지 덱에 사람 추가
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            deque.offer(i);
        }
        
        // 덱에 사람을 하나씩 제거
        while (deque.size() > 1) {
            deque.pollFirst();  // 첫 번째 사람 제거
            deque.offerLast(deque.pollFirst());  // 그다음 사람을 뒤로 보냄
        }
        
        // 마지막 남은 사람 출력
        bw.write(deque.peek() + "\n");
        
        bw.flush();
        bw.close();
        br.close();
    }
}

 

요세푸스 문제는 덱을 활용한 전형적은 문제로 Deque 자료구조를 사용하면 매우 효율적으로 해결할 수 있습니다.

사람을 하나씩 제거하는 과정에서 덱의 특성을 활용할 수 있는 문제였습니다.

 

---

공부하면서 유용했던 부분 메모 겸 공유하고자 끄적입니다.

고쳐야 하는 부분 있다면 댓글 남겨주시면 수정하겠습니다.

행복한 하루 보내세요 (❁´◡`❁)