[BOJ - 1158번] 조세퍼스 문제 - JAVA 정리 및 해설

간간히 올리는 백준해설 문제를 진행하려고 합니다. 틈틈히 제가 좀 정리가 필요한 경우, 이런식으로 블로그에 정리를 해서 올리겠습니다.

문제는 조세퍼스 순열을 구하는 문제로, 순번 찾기 즉, 수건돌리기처럼 제 순번에 잘 튀어 나오는 게 핵심입니다.  

그럼 잘 구하면 되는데, 뭐가 문제냐면, 그 순번이 끝지점에 갔을때 원래 위치로 돌아와야하는데, 그게 잘 안됩니다. ㅂㄷㅂㄷ...

즉, 원래 순번으로 다시 돌아오게끔 해주는 작업을 해야한다는 것이죠.  

일단, 저는 무식한 방법(Brutal Force)를 이용해서 한번 다 때려 보기로했습니다.

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {




	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);


		int n = input.nextInt();
		Queue<Integer> jo = new LinkedList<Integer>();
		int m = input.nextInt();
		int q[] = new int[n];
		for(int i=0; i<n; i++){
			q[i] = i+1;
		}
		boolean check = true;
		int tc = 0; //totalCheck
		int count =1;
		int	index = 0; //q[n]
		while(check){
			for(int j=0; j<n; j++){
				if(q[j]==-1){
					tc++;
				}
			}
			if(tc==n){
				check=false;
			}
			tc=0;
			index++;
			if(index==n){
				index = 0;
			}
			if(q[index]!=-1){
				count++;
			}
			if(count%m==0){
				if(q[index]!=-1){
					jo.offer(q[index]);
				}
				q[index]=-1;
			}


		}
		System.out.print("<"+jo.poll());
		while(!jo.isEmpty()){
			System.out.print(", "+jo.poll());
		}
		System.out.print(">");
	}


}
  

 이 코드문의 풀이 방식은 이렇습니다. 일단 입력값으로 예시를 들죠. 

◎ 1 2 씩 하나씩 옮기면서 count 를 올립니다. 

◎ 3 하면 3이 전체 TotalCount를 하나씩 올립니다..  

◎ 튀어나온 곳에는 -1을 집어 넣어서 이 순열의 중복으로 같은 수가 나오는 것을 방지합니다. 

◎ 4 5 6이 튀어 나오고 같은 방식으로, -1을 넣고

◎ 다시 순열을 진행시키면 7에 도달하면, 다시 1로 돌아갑니다.  

◎ 단, -1을 발견하면 count를 진행시키지 않고, 그냥 다시 반복문을 진행시킵니다. 

◎ 그러면서 count == m의 배수임을 알 수 있게 count%m ==0인 경우를 만들었습니다.

◎ 마지막으로 , totalcount와  전체 크기가 같으면 이 반복문을 종료 시킵니다. 

이러고 큐에 넣었던 모든 수를 다 뱉어내면 조세퍼스 순열이 나옵니다. 

하지만, 이 코드는 틀렸습니다.. ㅠㅠ

왜냐하면 시간초과가 걸리거든요. 이문제의 치명적 함정은 모든 수를 다 찾는 것에 있습니다. 

전체 수 사이즈가 커지면, 점점 제가 찾아야할 횟수가 늘어나서 시간 횟수가 커집니다. 즉, 전체 수가 줄지를 않아서 계속 그 크기를 계속 찾는 다는 겁니다.

그래서 여기 주어진 사이즈인 5000번을 정말 횟수를 어마어마하게 많이 루프를 돌게 되어서 시간 초과가 나게되죠.

그럼 다른 방법은 뭘 할까요?

큐를 통해서 순서를 회전하는 방법을 얻어 냈는데요. 일단 코드를 보실께요.

package codeBaekJoon; @@ 되는 코드@@
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class no1158_Josephus {
	
	
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		
		int n = input.nextInt();
		Queue<Integer> jo = new LinkedList<Integer>();
		Queue<Integer> jos = new LinkedList<Integer>();
		int m = input.nextInt();
		for(int i=0; i<n; i++){
			jo.offer(i+1);
		}
		int count =1;
		while(!jo.isEmpty()){
			
			if(count%m==0){
				jos.offer(jo.poll());
			}
			if(count%m!=0){
				jo.offer(jo.poll()); // 뺏다가 다시 넣으면 순서가 원래대로 돌아감.
			}
			count++;
		}
		System.out.print("<"+jos.poll());
		while(!jos.isEmpty()){
			System.out.print(", "+jos.poll());
		}
		System.out.print(">");
	}

}

단순하게 생각해보면, Queue에서 count%m을 하고 0일될때만 출력을 위한 큐에 넣어주고,

자기 순번이 아닌경우에는 넣다가 빼주기만해도. 자기 원래순서에 들어가게됩니다. 

여기서 잘 가져가야될 개념은 순번이 필요한경우 큐로 구현시 넣었다가 빼면 그 원래 순서는 지켜진다는 점 입니다. 

이런식의 짧지만, 간단한 코딩 스킬은 나중에 써먹으면 좋을 것 같습니다. 

감사합니다.