JAVA [Algorithm] - 백준 1158 요세푸스 문제

 

📝문제 설명

 

---

📢입출력 예시

 

---

✏️문제 풀이

처음에는 boolean 배열을 사용해 true, false 처리를 하여 인덱스 값을 응용해 사용하려 했지만, 제거 되는 문자가 적어질 수록 조건이 까다로워 다른 방법을 생각

 

K번째 사람들 제거하는 방법이면, 큐를 사용해 K-1번만큼 앞에 있는 숫자들을 뒤로 보내고, K번째를 poll하여 출력한다.

 

K = 3 일때

{1 2 3 4 5 6 7} 이렇게 있다면

 

K=1 {2 3 4 5 6 7 1}

K=2 {3 4 5 6 7 1 2}

K=3 {4 5 6 7 1 2} -> 3출력

 

K=1 {5 6 7 1 2 4}

K=2 {6 7 1 2 4 5}

K=3 {7 1 2 4 5} -> 6출력

 

이런 식으로 뒤로 보내는 방법을 사용했다.

 

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

public class Baek1158 {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

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

        Queue<Integer> queue = new LinkedList<>();

        for(int i=1; i<=N; i++){
            queue.offer(i);
        }

        System.out.print("<");

        while(queue.size() > 1){
            for(int i=0; i<K-1; i++){
                int temp = queue.poll();
                queue.offer(temp);
            }
            System.out.print(queue.poll() + ", ");
        }
        System.out.print(queue.poll() + ">");
    }
}

---

💡새로 알게된 점

 

---