[Baekjoon] 11866 - 요세푸스 문제 0

📝 문제

 

 

 

🔑 풀이 과정

· N명의 사람이 원을 이루며 앉아있다.

· 제거 된 위치로부터 K번째 사람을 제거한다. (문제에는 명시되어 있지않지만 원을 이루며 앉아있다 + 예제 1을 보면 알 수 있다.)

 

원형 큐를 구현해서 문제를 해결할 것이다.

 

(K-1)번 맨 앞 원소를 맨 위로 옮기고, 그 후 맨 앞 원소를 제거한다.

이러면 제거 된 위치로부터 K번째 원소가 제거 가능하다.

→ 이것을 계속 반복

 

출력같은 경우 다른 원소같은 경우는 "원소, " 형식을 유지하나, 마지막 제거되는 원소는 뒤에 띄어쓰기를 하면 안되므로

while 반복문의 조건을 !queue.isEmpty() 가 아닌 queue.size() != 1을 해서 원소 1개를 남겨준다.

그 후 반복문 탈출 후 1개남은 원소를 출력한다.

 

그림으로 표현한 풀이

 

 

 

🔓 답안

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

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));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        //1부터 N까지 큐 채우기
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 1; i <= N; i++){
            queue.add(i);
        }

        bw.write("<");
        while(queue.size() != 1){
            for(int i = 1; i < K; i++){
                queue.add(queue.remove());
            }

            bw.write(queue.remove() + ", ");
        }

        bw.write(queue.remove() + ">");

        bw.flush();
        bw.close();

    }

}

 

 

 

🖤 알고리즘 분류

- 구현

- 자료 구조

- 큐