[ Algorithm ] 백준 11866번 : 요세푸스 문제 0 - [JAVA]

🎆백준 11866번 요세푸스 문제 0🎆

---

📌문제

🔍문제 설명

문제 링크: https://www.acmicpc.net/problem/11866

🔍예제 입력

7 3

🔍예제 출력

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

---

📌풀이

🔍풀이 설명

자료 구조 (Date-Structure)를 이용하여 푸는 문제였다. Queue 사용

Queue : Queue(큐)는 순서를 따르는 자료구조
Queue(큐)는 앞(front)과 뒤(back)가 존재하며, 먼저 들어온 데이터가 먼저 빠져 나가는 선입선출(First-in-First-out)의 규칙을 따른다.

• poll(): 큐에서 front에 위치한 객체 리턴 후 제거(dequeue).
• offer(item) or add(item): item 하나를 큐의 가장 뒷 부분에 추가한다.
• peek(): 큐에서 front에 위치한 항목을 반환한다.
• isEmpty(): 스택이 비어 있을 때에 true를 반환한다.
• remove(E e): 특정 객체 E 제거 (e없을 때 제일 front객체 제거)

큐의 성질을 이용해 K-1번째 사람은 큐에 다시 추가하고 K번째 사람은 제거하는 반복문을 구현했다. 이 반복문은 큐의 크기가 0이 될 때까지 반복한다.

🔍코드

package Data_Structure;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

//요세푸스 문제 0
public class p11866 {
    static Queue<Integer> queue;
    public static void main(String[] args)throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        queue = new LinkedList<>();
        sb.append("<");
        for(int i=1; i<=N; i++){
            queue.add(i);
        }
        while (!queue.isEmpty()){
            int number=0;
            for(int i=0; i<K-1; i++){
                number = queue.remove();
                queue.add(number);
            }
            //K번째 수를 제거할 때 큐의 사이즈가 1인 경우 (숫자가 하나만 남음) : 바로 제거
           if(queue.size() == 1){
               sb.append(queue.remove());
           }
           //K번째 수를 제거함
           else{
               sb.append(queue.remove()).append(", ");
           }
        }
        sb.append(">");

        System.out.print(sb);
    }
}

---

👋마무리👋

시작할 때 "<", queue의 size가 1일 때 값을 제거하면 ,가 없어야하기 때문에 따로 조건을 넣었구.. 반복문이 끝났을 때 ">"로 마무리 .. 이렇게 출력형식을 맞춰야해서 StringBuilder로 출력 형식을 맞췄당 ㅎ 재밌엉 ㅎ..! 앗 글고 자바에서 Queue 이용하려면 LinkedList<>()로 선언해야한다는 점!!! 중요중요