[문제풀이] 백준 #11866 요세푸스 문제 Java 풀이

👉 문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력:
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

출력:
예) <3, 6, 2, 7, 5, 1, 4>

✨ 풀이

import java.util.*;

public class JosephusProblem {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        // N, K 받기
        int num = sc.nextInt();
        int mark = sc.nextInt();


        // Queue로 풀기

        // 1부터 num까지의 수로 queue 채우기
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 1; i <= num; i++) {
            queue.offer(i);
        }

        // 반복시 사용할 카운트 생성
        int count = 0;
        // 반환할 결과값 생성
        String res = "<";
        // queue가 빌 때까지
        while (!queue.isEmpty()) {
            count++;
            // 카운트가 주어진 mark수와 같을 경우 결과값에 추가하고 카운트 초기화
            if(count == mark) {
                res += queue.poll() + ", ";
                count = 0;
            }
            // 카운트!=mark인 경우 poll한 값을 다시 queue에 추가
            else{
                queue.offer(queue.poll());
            }
        }
        // 결과값 맨뒤의 ", " 제거한 후 부등호로 닫아서 정해진 양식에 맞게 수정
        res = res.substring(0, res.length()-2);
        res += ">";

        System.out.println(res);


    }
}

풀이 방식:

Queue로 풀어야겠다는 생각이 처음부터 들지는 않았다. for문을 이용해 배열을 생성하고, StringBuilder와 for문과 if문을 적절히 사용해서 풀려고 했다. 그러나 주어진 mark 수만큼 순회하는 것까지는 구현이 되는데, 결과값에 추가된 값을 건너뛰는 방법을 떠올리지 못해 막혔다. (이것도 더 고민해보면 방법이 있겠지만, Queue에 비하면 상당히 비효율적인 방법 같다.)

그러던 중 하나씩 빠져나가게 해야 하는 것이 Queue와 같다는 생각이 떠올라서 활용했더니 풀렸다. 너무 손에 익은 풀이 방법을 우려먹으려고 하지 말고 다양한 접근을 고민해봐야겠다고 느꼈다. 가물가물하다면 책과 검색으로 다시 익혀가며 배운 것을 충분히 활용하자,,🦾