[BOJ - JAVA] 11866 - 요세푸스 문제 0 (큐)

# 주소

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

11866번: 요세푸스 문제 0

# 문제

# 문제 해설 및 코드 리뷰

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        Queue<Integer> queue = new LinkedList<Integer>();
        for(int i = 1; i <= n; i++){
            queue.add(i);
        }
        int[] arr = new int[n];
        int start = 0;
        int t = 1;
        while(!queue.isEmpty()) {
        	int x = queue.poll();
        	if(t == m) {
        		arr[start] = x;
        		start++;
        		t = 0;
        	}
        	else {
        		queue.add(x);
        	}
        	t++;
        }
        System.out.print("<" + arr[0]);
        for(int i = 1; i < n; i++) {
        	System.out.print(", " + arr[i]);
        }
    	System.out.print(">");
    }
}

이번엔 큐를 활용하는 문제를 가져왔습니다.

만약 입력되는 값이 7 3일 때 1~7까지의 자연수를 원에 순서대로 배열한다고 가정합시다.

그리고 3번째 사람마다 그 해당 값을 저장해서 출력하면 되는데요. 처음에 3부터 시작하여 3 6 그다음 7다음은 1이므로 2가 저장되고, 다시 7, 5 1 4 순서로 값이 저장됩니다.

그러므로 일단 큐에 자연수들을 먼저 집어넣습니다. 1부터 n까지 모두 넣어야 합니다. 

그리고 나서 int타입의 arr를 선언하는데, 이 arr에 3번째 값마다의 큐 값을 넣을 것입니다.

 

이후 start = 0, t = 1로 선어하는데, 여기서 start는 arr의 index입니다.

그리고 t는 순수히 queue의 index라고 보면 되겠습니다. 

그리고 while(!queue.isEmpty())라고 입력하면 큐가 비어있지 않을때까지 계속 while문을 사용한단 뜻이므로 큐를 이용하여 문제를 풀 때는 항상 빠지지 않고 나오는 구문이니까 잘 알아두세요!!

while문 내부구조로 들어가, int x = queue.poll()를 하는데요. 여기서 x란 queue에서 가장 먼저 들어갔던, 그러니까 1을 가져오는 겁니다. 그리고 t == m일 때(queue가 m번째 숫자가 됐을 때) arr에 x를 넣고 start를 증가시킨 후 t = 0으로 초기화합니다. 

그러나 t != m이라면 해당 queue의 값은 m번째 숫자가 아니므로 다시 queue에 넣습니다. 그러므로 위의 예제에 빗대어 살펴보면, 1 2 3 4 5 6 7에서 1은 3번째 숫자가 아니므로 2 3 4 5 6 7 1 이런식으로 큐가 바뀌는 것입니다. 그러면 이어서 queue.poll()해서 나온 2도 m번째 숫자가 아니므로 3 4 5 6 7 1 2 이렇게 queue가 바뀔테고요. 마지막으로 3은 m번째 숫자이므로 3을 arr에 담고 3을 빼내온 후 4 5 6 7 1 2 로 queue를 만들고 start++, t = 0으로 다시 만들어주는 작업을 해야만 하는 것입니다. 

그렇다면 arr에는 원하는 정답이 실려있을 겁니다!

감사합니다.