[Java] 백준 1158번 - 요세푸스 문제

문제 링크 : 백준 1158번 - 요세푸스 문제

 

이런 문제를 마주쳤을 때 가장 먼저 할 것은 어떤 자료구조를 사용할 것이느냐이다.

크게 스택과 큐 중 하나를 고를 수 있는데, 이 문제에서는 큐(FIFO)를 사용하는 것이 적절하다.

 

자바에서는 ArrayDeque를 사용하면 되고, N명의 사람을 삽입해준다.

    ArrayDeque<Integer> list = new ArrayDeque<>();
    for (int i = 1; i <= N; i++) {
        list.add(i);
    }

 

 

출력을 위한 StringBuilder를 만들어주고, 사람이 빌 때까지 반복한다.

중요한 것은 사람이 K명보다 적어지더라도 K번째 사람이 사라져야 하기 때문에, 다음과 같이 K-1명 만큼 리스트에서 제거해 다시 넣어준 후 K번째 사람을 제거해주면 된다. 이러면 원형으로 계산을 할 수 있다. FIFO의 자료구조를 생각해보면, 제일 먼저 들어간 것이 제일 먼저 나오므로 제일 앞에 있는 사람이 나와 제일 뒤로 갈 것이기때문에 원형으로 자료의 순서가 유지된다.

StringBuilder sb = new StringBuilder("<");
while (!list.isEmpty()) {
    for (int i = 0; i < K - 1; i++) {
        list.add(list.remove());
    }
    sb.append(list.remove());
    sb.append(!list.isEmpty() ? ", " : "");
}
sb.append(">");
System.out.println(sb);