백준 1158번 조세퍼스 문제 :: 마이구미

이번 문제는 백준 1158번 조세퍼스 문제를 다룰 것이다.

이미 요세푸스의 문제로 많이 알려져있는 대중화된 문제이다.

Github - https://github.com/hotehrud/acmicpc

조세퍼스 문제는 다음과 같다.

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

N과 M이 주어지면 (N,M)-조세퍼스 순열을 구하는 프로그램을 작성하시오.

본인은 보자마자 그냥 원이니까 원형큐로 풀어야지 생각했다.

하지만 막상 구현하고 해보니 흠..... 조금 까다로웠다.

그래서 차근차근 생각해보았다.

1, 2, 3, 4, 5, 6 ......... n-2, n-1, n이 있다고 해보자.

잔인하지만 3번째 순서를 계속 죽인다고 해본다면 처음에 죽이면 4번째 있는 사람이 첫번째 순서가 된다.

그리고 1, 2번째는 있던 사람들은 순서가 아래와 같이 뒤로 밀리는 것을 알 수 있다.

4, 5, 6 ....... n-2, n-1, 1, 2

흠.. 뭔가 느낌이 온다! 한번 더 죽여보자. 6이 죽는다.

7, 8, 9 ..... n-2, n-1, 1, 2, 4, 5 와 같이 된다.

그렇다면 그냥 죽이고, 앞에 있는 것들을 뒤로 다시 넣어주면 되지 않은가?

큐나 데큐를 이용해서 앞에 있는 것을 팝시키고 뒤로 푸시하면 되는 것이다.

그러면 간단히 문제가 해결 된다.

흠... 근데 뭔가 비효율적으로 보일 것으로 생각한다.

맞다.. 뺐다 넣고 뺐다 넣고 데이터가 크면 클수록 퍼포먼스 측면에서는 매우 안좋다.

다른 방법을 생각해보자.

문제에서는 M번째를 죽인다. 규칙이 존재한다.

문제를 풀 때 어떠한 패턴이 존재한다면 나머지(%) 연산으로도  한 번 해볼 수 있다는 생각을 하길 바란다.

두 가지의 소스를 올려놓겠다.

조세퍼스 문제는 많이 존재한다.

위의 방법으로 몇문제 정도는 풀 수 있다.

하지만 난이도가 높은 조세퍼스 문제일수록 다른 방법으로 접근해야한다.

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

pop 후 push를 활용한 방식

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Deque<Integer> deque = new ArrayDeque<Integer>();
         
        StringBuilder sb = new StringBuilder("<");
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
         
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
 
        for(int i=1;i<=n;i++) {
                deque.add(i);
        }
         
        while(!deque.isEmpty()) {
                for(int i=0;i<m-1;i++) {
                    deque.addLast(deque.removeFirst());
            }
            sb.append(deque.removeFirst() + ", ");  
        }
        System.out.println(sb.toString().substring(0, sb.length()-2) + ">");
    }
}

나머지 연산을 활용한 방식

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		ArrayList<Integer> list = new ArrayList<Integer>();
		
		StringBuilder sb = new StringBuilder("<");
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken()) - 1;

        for(int i=1;i<=n;i++) {
        		list.add(i);
        }
        
        int index = 0;
        
        while(!list.isEmpty()) {
	        	index += m;
	        	
	        	if (index >= list.size()) {
	        		index %= list.size();
	        	}
	        	
	        sb.append(list.remove(index) + ", ");	
        }
        System.out.println(sb.toString().substring(0, sb.length()-2) + ">");
	}
}