[백준 Java] 20301번 반전 요세푸스 (구현)

 

[Silver III] 반전 요세푸스 - 20301

문제 링크

성능 요약

메모리: 19772 KB, 시간: 308 ms

분류

자료 구조, 덱, 구현, 시뮬레이션

문제 설명

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

 1번 사람 오른쪽에는 2번 사람이 앉아 있고, 2번 사람 오른쪽에는 3번 사람이 앉아 있고, 계속하여 같은 방식으로 N명의 사람들이 원을 이루며 앉아 있다. N번 사람 오른쪽에는 1번 사람이 앉아 있다. 이제 K(≤N)번 사람을 우선 제거하고, 이후 직전 제거된 사람의 오른쪽의 K번째 사람을 계속 제거해 나간다. 모든 사람이 제거되었을 때, 제거된 사람의 순서는 어떻게 될까?

이 문제의 답을 (N, K)–요세푸스 순열이라고 하며, (7, 3)–요세푸스 순열은 ⟨3,6,2,7,5,1,4⟩가 된다.

하지만 한 방향으로만 계속 돌아가는 건 너무 지루하다. 따라서 요세푸스 문제에 재미를 더하기 위해 M명의 사람이 제거될 때마다 원을 돌리는 방향을 계속해서 바꾸려고 한다. 이렇게 정의된 새로운 문제의 답을 (N, K, M)–반전 요세푸스 순열이라고 하며, (7, 3, 4)–반전 요세푸스 순열은 ⟨3,6,2,7,1,5,4⟩가 된다.

 N, K, M이 주어질 때, (N, K, M)–반전 요세푸스 순열을 계산해 보자

입력

첫째 줄에 정수 N, K, M이 주어진다. (1≤N≤5 000, 1≤K,M≤N)

출력

(N, K, M)–반전 요세푸스 순열을 이루는 수들을 한 줄에 하나씩 순서대로 출력한다.

💡 나의 접근

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

1158번: 요세푸스 문제

이 문제의 이어지는 문제이니 안풀었다면 풀어보길 바란다.

굳이 안풀어도 풀수 있긴하다. 

 

나는 자료구조를 ArrayList를 사용했다.

요세푸스 순열을 찾아내는 Josephus() 함수를 두었다.

파라미터 idx 는 어디서부터 탐색을 시작할지 알려주는 변수이다.

 

N의 크기를 봤을때 5000밖에 되지 않았고 N^2도 가능할 것 같아서 

for문을 이용해서 idx를 1씩 증가시켜 K번만큼 반복하는데

이때 idx가 남아있는 숫자의 갯수를 넘어간다면 idx=0으로 두어 원형으로 탐색할 수 있게 하였다.

그렇게 해서 제거할 인덱스(idx)를 알아낸 후 Arraylist에서 제거하였다.

이때 count라는 변수를 두어 제거 할때마다 1씩 증가시켜주었고

count가 M과 같아진다면 반대 방향으로 탐색하는 JosephusReverse () 함수를 호출하도록 하였다.

 

 

이 함수에서는 1씩 감소시키는 작업을 K번 만큼 반복하는데 

idx가 0보다 작아진다면 남아있는 숫자들 중 가장 마지막의 숫자를 가르킬수 있도록 하였고 

위와 동일하게 제거할때마다 count를 증가 시켜서 M과 같아진다면 다시 Josephus를 호출하도록 했다.

 

 

큐를 써야하는 문제인지는 알고리즘 분류를 보고서야 알았다 ㅋㅋㅋㅋㅋ

아직은 생각해내는 자료구조가 한정적인가보다

뭐.. 아무렴 어때 

문제가 풀리기만 하면 됐지 ㅋㅋㅋㅋ

 

아, 심지어 큐를 사용한 코드보다 시간은 짧은거 같다.

 

💡 코드

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

public class Main {
	static int N;
	static int K;
	static int M;
	static ArrayList<Integer> num = new ArrayList<>();
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());


		for (int i = 1; i <= N; i++) {
			num.add(i);
		}

		Josephus(-1);

		System.out.println(sb.toString());

	}
	static void Josephus(int idx) {
		int count =0;
		while (!num.isEmpty()) {
			for (int i = 0; i < K; i++) {
				idx ++;
				if(idx >= num.size()) {
					idx = 0;
				}
			}
			sb.append(num.get(idx)).append("\n");
			num.remove(idx);
			count++;
			if(count == M) {
				JosephusReverse(idx);
			}
			idx--;

		}

	}
	private static void JosephusReverse(int idx) {
		int count =0;
		while (!num.isEmpty()) {
			for (int i = 0; i < K; i++) {
				idx --;
				if(idx < 0) {
					idx = num.size()-1;
				}
			}
			sb.append(num.get(idx)).append("\n");
			num.remove(idx);
			count++;
			if(count == M) {
				Josephus(idx-1);
			}

		}
	}
}