[테코테코1.5 4-07] 요세푸스 문제

💡테코테코 시즌 1.5 4회 모임 on-site 문제 풀이입니다. (2025.02.15)

 

문제

출처: 백준 - 요세푸스 문제

 

내용

 

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

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

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

 

기록하기

💡 어디까지 생각해봤는지 단계적으로 기록해봅니다.

어떤 알고리즘을 적용하려 했나요?

원형 큐를 적용한다.

적용 근거는 무엇인가?

"원을 이루면서 앉아있다."

문제 풀이 과정에서 해당 알고리즘을 어떻게 코드로 구현하려 했나요?

모듈러 연산은 사용하지 않고 deque, enque를 활용한다.

 

풀이

풀이 시간

시작 시각	종료 시각	총 소요 시간
		15분

 

문제 분석

제약 사항 파악 & 입력값 분석

💡 입력값을 분석하면 문제에서 요구하는 알고리즘의 시간 복잡도를 간접적으로 파악할 수 있습니다.

입력

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

출력

예제와 같이 요세푸스 순열을 출력한다.

 

예제 입력1

7 3

예제 출력1

<3, 6, 2, 7, 5, 1, 4>

 

 

의사 코드 작성

💡 의사 코드는 동작 중심으로 작성하는 것이 중요합니다.

💡 의사 코드는 문제 해결 순서로 작성합니다.

💡 의사 코드를 충분히 테스트해봅니다.

solution(n, k) {
    // 1234567 -> 456712 -> 71245 -> 4571 -> 145
    // enque, deque 활용
    // k번째 수는 deque만 그 외는 deque 후 enque
}

 

 

구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bufferedReader.readLine(), " ");
        StringBuilder answer = new StringBuilder("<");

        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        ArrayDeque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            queue.add(i + 1);
        }

        // 1234567 -> 456712 -> 71245 -> 4571 -> 145
        int count = 1;
        int front;
        while (!queue.isEmpty()) {
            front = queue.poll();
            if (count == k) {
                answer.append(front);
                if (!queue.isEmpty()) {
                    answer.append(", ");
                }
                count = 1;
                continue;
            }
            queue.add(front);
            count++;
        }

        answer.append(">");
        System.out.println(answer);
    }
}