[Java] 조세퍼스 문제

1. 문제 설명

N명의 사람이 원 모양으로 둥글게 앉아있으며, 각각 시계방향으로 1~N번의 번호를 부여받는다고 하자. 아래와 같은 규칙으로 사람들을 제외해 나간다.

• 가장 처음에는 1번 사람이 지목된다.
• 이후 시계방향으로 다음 사람이 지목된다.
• 이를 반복하다가 M번째로 지목받은 사람을 제외한다. 그 이후 제외 된 사람의 다음 사람부터 위의 과정을 반복해 나간다.

예를 들어서 N=7이고 M=3인 경우를 생각해보자.
초기에는 { 1, 2, 3, 4, 5, 6, 7}처럼 사람들이 앉아있다.
3번째로 지목되는 3번을 제외하여 { 1, 2, 4, 5, 6, 7 }이 남으며 4번부터 게임을 다시 시작한다.
차례로 4, 5, 6번 사람이 지목받아 3번째로 지목받은 6번이 게임에서 제외되므로 { 1, 2, 4, 5, 7 }의 사람이 남아 게임을 다시 시작한다.
차례로 7, 1, 2번 사람이 지목받아 3번째로 지목받은 2번이 게임에서 제외되므로 {1, 4, 5, 7 }의 사람이 남아 게임을 다시 시작한다.
...

위와 같은 과정을 반복한다고 하자. N과 M이 주어졌을 때 각 번호의 사람들이 게임에서 제외되는 순서대로 출력하는 프로그램을 작성하시오.

입력 형식

첫 줄에는 테스트케이스의 수를 나타내는 10이하의 자연수 T가 주어진다. 이후 총 T개에 대한 입력이 차례로 주어진다.

각 테스트케이스의 입력은 한 줄로 N M형식으로 주어진다.

N은 사람의 수를 나타내는 5,000이하의 자연수다.
M은 사람을 제외해 나갈 간격을 나타내는 5,000이하의 자연수다.

출력 형식

각 테스트케이스별로 한 줄에 정답을 출력한다.

N명의 사람들의 번호를 제외 된 순서대로 출력한다.
각 번호는 공백으로 구분한다.

2. 알고리즘 접근

게임에서 제외된 사람을 고려햐여 순회하면 굉장히 느려진다.
즉, 게임에서 제외된 사람을 고려하지 않고 순회하기 위해 Queue 자료구조를 사용한다

Queue의 특징

• 순차적으로 데이터를 저장하며, 가장 앞, 뒤의 원소 접근이 가능한 자료구조
• 스택과 다르게 먼저 삽입된 원소가 먼저 삭제됨(FIFO)

Queue의 사용

[3, 5, 6, 7, 10, 12, 1, 2]를 순회한다
대상 '3'은 3번째가 아니니 pop()하고 push()하여 스택의 맨뒤로 옮긴다
대상 '2'은 3번째가 아니니 pop()하고 push()
대상 '6'은 3번째니 pop()-> 이를 무한 반복하면 된다

3. 소스 코드

 import java.io.*;
import java.lang.*;
import java.util.*;


public class Main {
	public static final Scanner scanner = new Scanner(System.in);

	/**
	 * 조세퍼스 게임을 수행하여 각 플레이어가 제거된 순서를 리스트로 반환하는 함수
	 *
	 * @param n         플레이어의 수
	 * @param m         매 턴마다 건너 뛸 사람의 수
	 * @param players   좌석에 앉아있는 순서대로 주어지는 플레이어 정보
	 * @return
	 */
	public static ArrayList<Player> getDeadPlayersList(int n, int m, Player[] players){
		// 현재 게임에서 제외된 플레이어들의 리스트
		ArrayList<Player> deadPlayers = new ArrayList<>();

		// 아직 게임에서 제외되지 않는 플레이어들의 리스트
		Queue<Player> playerQueue = new LinkedList<>();
		for(Player p : players){
			// 모두 차례로 한 번씩
			playerQueue.add(p);
		}
		for(int i = 0; i < n; i++){ // 총 n라운드 반복
			int j = 1 + (m - 1) % playerQueue.size(); // 1based를 위함 (점프 수)
			for(int k = 0; k < j -1; k++){
				Player p = playerQueue.poll(); // 맨 앞을 빼준다.
				playerQueue.add(p); // 뺀 값을 맨 뒤로 다시 넣는다
			}
			Player p = playerQueue.poll();
			deadPlayers.add(p);// 점프 한 값을 제외
		}
		

		return deadPlayers;
	}

	public static void testCase(int caseIndex) {
		int n = scanner.nextInt();
		int m = scanner.nextInt();

		Player[] players = new Player[n];
		for(int i = 0 ; i < n ; i++)
		{
			players[i] = new Player(i+1);
		}

		ArrayList<Player> deadPlayers = getDeadPlayersList(n,m, players);

		for(int i = 0 ; i < n ; i ++){
			if( i > 0 ){
				System.out.print(" ");
			}

			Player p = deadPlayers.get(i);
			System.out.print(p.index);
		}
		System.out.println();
	}

	public static void main(String[] args) throws Exception {
		int caseSize = scanner.nextInt();

		for (int caseIndex = 1; caseIndex <= caseSize; caseIndex += 1) {
			testCase(caseIndex);
		}
	}

}

class Player{
	public final int index;

	public Player(int index){
		this.index = index;
	}
}