[코딩테스트] 백준 1158번 요세푸스 문제 - JAVA

https://www.acmicpc.net/problem/1158

 

Problem 💻

문제

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

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 ≤ 5,000)

출력

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

 

 

Solution 💡

요세푸스문제는 두 가지 방법으로 접근이 가능하다. 큐와 연결리스트를 통해 문제를 해결할 수 있다.

큐

큐도 접근하는 방법은 원형 큐에 방식을 이용해야한다.

큐에 기본적으로 제공되는 입력  n 의 값을 넣은 후, k 번째 위치를 지속적으로 찾아야한다.

• 처음과 끝의 값이 연결되어 있어야 하므로 k-1 번째 값들을 다시 add() 하여 뒤로 삽입하는 과정을 통해 원형 구조를 흉내내는 방식이다.
• 이 방식은 배열 기반 원형 큐처럼 공간 제약이 없으며, 논리적인 원형 구조로 동작하게 된다.

package backjoon.silver.lv4;

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 B1158 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

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

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

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

        StringBuilder sb = new StringBuilder();
        sb.append("<");
        while (!queue.isEmpty()) {
            // 큐를 이용하여 원형 데이터를 유지하는 방법
            // 원하는 값 이외 값들은 다시 큐에 넣어줘야 한다.
            for (int i = 0; i < k -1; i++) {
                queue.add(queue.poll());
            }
            // 조건에 맞는 k번째 값
            sb.append(queue.poll());

            // 마지막을 제외한 나머지 (, ) 추가
            if (!queue.isEmpty()) {
                sb.append(", ");
            }
        }

        // 출력
        sb.append(">");
        System.out.println(sb);
    }
}

연결리스트

다음과 같은 방식으로 진행된다.

1. 연결리스트를 우선 1부터 N까지 초기화하여 값을 삽입한다.
2. 현재 위치로 부터 K-1번씩 이동하여 삭제할 사람을 선택한다. (인덱스이기 때문에 -1를 해준다.)
3. 선택된 사람을 리스트에서 제거하고 요세푸스 순열에 추가한다.
4. 리스트가 비었을 때까지 반복한다.

여기서 주의할 점이 삭제할 인덱스를 구하는 부분이다. 요세푸스 순열같은 순환 회전문제에선 점화식을 구하는 것이 중요하다.

list=[1,2,3,4,5,6,7],K=3

계산과정 
index = 0 (시작위치)

1. index = (0 + 3 - 1) mod 7 = 2 -> 3 삭제, list=[1,2,4,5,6,7]
2. index = (2 + 3 - 1) mod 6 = 4 -> 6 삭제, list=[1,2,4,5,7]
...

 

위와 같은 방식으로 진행되는 것을 알 수 있다. 최종적으로 다음과 같은 인덱스를 구하는 점화식을 유추할 수 있다.

index = (index + k - 1) % list.size()

 

점화식을 구하고 나면 삭제할 인덱스를 찾을 수 있는 것이니깐 해당 인덱스를 문자열에 추가하고 삭제처리 하면서 루프가 끝날 때 까지 진행하면 된다.

package backjoon.silver.lv4;

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

/**
 * 연결리스트 활용
 */
public class B1158_1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            list.add(i + 1);
        }

        StringBuilder sb = new StringBuilder();
        sb.append("<");

        int index = 0;
        while (!list.isEmpty()) {
            // 원형 큐, 회전초밥 ...
            // 인덱스의 k번째를 더하되 인덱스이기 때문에 -1 처리
            // n값을 넘으면 안되니깐 n으로 나눈 나머지 값을 이용
            // 대신 remove가 들어가므로 줄어진 리스트 사이즈 값을 기준으로 함
            index = (index + k - 1) % n;
            sb.append(list.get(index));
            list.remove(index);

            if (!list.isEmpty()) {
                sb.append(", ");
            }
        }

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

}

 

 

Reference 📄

- 요세푸스, 원형 문제에서 사용되는 점화식을 알아보자.