[JAVA] BOJ 1158 요세푸스 문제

 

원으로 앉아있다는건 배열을 순환한다는 것과 같다. 따라서 배열의 끝에 도착하면 다시 처음으로 돌아가도록 해주는 것이 핵심이다. 또한 K번째 사람을 제거한다는 것은 배열을 순환하면서 K번째를 방문했으면 넘어가도록 구현하였다.

 

독특한 출력형태로 input은 Scanner로 받고 출력은 BufferedWriter를 사용하였다.

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String st = sc.nextLine();
		int N = Integer.parseInt(st.split(" ")[0]);
		int K = Integer.parseInt(st.split(" ")[1]);
		boolean[] visited = new boolean[N];
		int idx=0;
		bw.write("<");
		for(int i=0; i<N;i++) {
			int pos=K;
			while(pos!=0) {
				if(idx>=N) idx=0;
				if(visited[idx]==false) {
					pos--;
				}
				idx++;
			}
			visited[idx-1]=true;
			if(i==N-1) bw.write(idx+">");
			else bw.write(idx+", ");
		}
		bw.flush();
		bw.close();
	}

}

 

방문 여부를 저장해주기위해 visited를 N의 사이즈에 맞게 boolean 타입으로 지정해주었다.

사람 수대로 반복문이 돌기 때문에 1차 반복문을 구현하고 pos라는 변수에 K를 저장하여 한 사람씩 이동할때마다 방문 여부를 체크하고 만약 방문하지 않았다면 pos를 차감해주어 pos가 0이되면 while 반복문을 빠져나가게 해주었다. K번 이동을 완료하면(while 반복문이 끝나면) 방문 처리를 한 후 idx값을 bufferedwriter에 쌓아준다.  

 

초기에 말한 배열의 순환을 구현하기 위해 idx라는 변수를 도입하여 만약 idx가 N보다 크거나 같아지면 0으로 초기화해주었다.