/ BOJ

BOJ_11866_요세푸스문제0_JAVA

문제 : 요세푸스문제0

링크 : BOJ_11866_요세푸스문제0

접근 방식

카드2 문제와 유사한 면이 있다. 모든 수가 큐에서 빠져나갈 때까지 단방향 순환을 시켜주면서 카운트를 세어 K번째마다 poll하여 저장하면 되는 문제이다. 다만, 다른 문제와 다르게 출력문에 ‘<’ ‘>’ ‘,’ 이 들어가기 때문에 이 부분은 주의할 필요가 있겠다.

풀이 방법

  1. Queue를 선언하여 LinkedList 객체를 생성한다.

  2. 1~N까지 Queue에 offer 해준다.

  3. 카운트 변수를 2개 두었다. 첫 번째 카운트는 주어진 K를 체크하여 K번째가 되었다면 poll해주도록 한다.

  4. 2번째 카운트는 모든 수가 빠져나갔는지 체크한다. 한번 poll 될 때마다 카운트를 증가시켜, N번째가 되면 반복문이 멈추도록 한다.

  5. 반복문 안에서, 첫 번째 카운트가 K-1과 같은 경우에는 큐를 poll하여 StringBuilder에 추가 해준다.

  6. 그렇지 않을 경우, 값을 poll해서 다시 큐에 offer하여 순환시켜준다.

  7. 두번째 카운트가 N-1일 경우, 이 때의 큐 안에 있는 데이터가 마지막 데이터라는 의미이므로 poll하고 반복문을 나간다.

  8. 저장된 StringBuilder를 출력한다.

소스 코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ_11866_요세푸스문제0 {

	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String[] str = in.readLine().split(" ");
		int N = Integer.parseInt(str[0]);
		int K = Integer.parseInt(str[1]);
		Queue<Integer> queue = new LinkedList<>();
		for(int i=1;i<=N;i++) {		
			queue.offer(i);
		}
		StringBuilder sb = new StringBuilder();
		int cnt = 0;
		int cnt2 = 0;
		sb.append("<");
		while(cnt2 <= N-1){
			if(cnt == K-1) {
				if(cnt2 == N-1) {
					sb.append(queue.poll());
				}else {
					sb.append(queue.poll()).append(", ");
				}
				cnt = 0;
				cnt2++;
			}else {
				int num = queue.poll();
				queue.offer(num);
				cnt++;
			}		
		}
		sb.append(">\n");

		System.out.print(sb);


	}

}