[백준: 알고리즘_Java] 1158번_요세푸스 문제

 

<문제>

 

 

이 문제는 사실.... 2학기 중간고사때 나온 문제와 거의 비슷함....

근데 내가 그때 문제를 잘못 이해해서 틀렸음...까비

이번에는 제대로 이해해 보는 것으로,... 개 쉬운 문젠데..

---

<풀이>

 

Queue 의 FIFO(First In First Out: 제일 먼저 저장한 것을 제일 먼저 꺼낸다.) 특징을 이용하면 됨.

 

순서대로 K번째 사람을 제거한다고 했으므로,,

K번째 전까진 꺼낸다음 다시 위에 쌓아주면 됨. (원으로 앉아있으니까)

K번째 사람은 ArrayList arr에 add해줌.

이걸 반복.

 

나는 try-catch문을 사용해서 queue의 값을 모두 꺼냈다면(=queue가 비었다면= NullPointException발생) 무한 반복문을 빠져나가도록 코드를 짰다.

 

출력은 arr를 String으로 바꿔주고 replace()를 이용해서 '[', ']' 를 각각 '<', '>'로 바꾸어 출력.

 

import java.util.*;
public class Josephus {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //N, K 입력받기
        int n = sc.nextInt();
        int k = sc.nextInt();

        Queue<Integer> que = new ArrayDeque<>();
        //결과 넣을 배열.
        ArrayList<Integer> arr = new ArrayList<>();
        int count  = 0;
        //1. que에 1~n 숫자 넣기
        //2. que에서 k번째 숫자까지 poll할 건데, k번째에 도달하기 전까진 poll한 뒤, 다시 add
        //3. k번째 숫자는 arr에 add

        //1.
        for(int i = 1; i <= n; i++) {
            que.add(i);
        }

        try {
            while(true) {
                for(int i = 1; i <= k; i++) {
                    //2.
                    int tmp = que.poll();
                    if(i < k) {
                        que.add(tmp);
                    } else {
                        //3.
                        arr.add(tmp);
                    }
                }
            }
        }catch (NullPointerException e) {

        }


        System.out.println(arr.toString().replace('[', '<').replace(']', '>'));


    }
}

 

---

<결과>