[BOJ] 백준 1158 요세푸스 문제

출처: https://www.acmicpc.net/problem/1158

 Input 

7 3

 

 Output 

<3, 6, 2, 7, 5, 1, 4>

 

배열에서 K번째 원소를 찾은 후, 제거된 순서대로 Queue에 넣어줍니다.

K 번째 원소를 찾을 때 원형 큐를 찾거나, 원소를 재배치하여 처리할 수 있습니다.

(※ 제출 코드에는 원소를 재배열하여 탐색)

---

import java.util.Scanner;
 
class Queue {
    int front, rear;
    int[] queue;
    public Queue(int size) {
        front = 0;
        rear = 0;
        queue = new int[size];
    }
    public void push(int value) {
        queue[rear++] = value;
    }
    public int pop(int idx) {
        int return_value = queue[idx];
        re_array(idx);
        return return_value;
    }
    // 배열 재배치
    public void re_array(int idx) {
        rear--;
        for (int i = idx; i < rear; i++) {
            queue[i] = queue[i + 1];
        }
        return;
    }
    // K 번째 원소 찾기
    public int find_idx(int m, int idx) {
        idx = idx + m - 1;
        if (idx >= rear) {
            idx = idx % rear;
        }
        return idx;
    }
 
    public void print_queue() {
        System.out.print("<");
        for (int i = front; i < rear; i++) {
            if (i == rear - 1) {
                System.out.print(queue[i]);
            }
            else {
                System.out.print(queue[i] + ", ");
            }
        }
        System.out.println(">");
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
 
        // n 개의 값을  큐에 대입
        Queue item_Q = new Queue(n);
        for (int i = 0; i < n; i++) {
            item_Q.push(i + 1);
        }
        // 입력 받은 m 에 대해서 주어진 순열(순서) 구현
        Queue result_Q = new Queue(n);
        int idx = 0;
        // 입력 받은 갯수 만큼 출력해야 하므로
        for (int i = 0; i < n; i++) { 
            idx = item_Q.find_idx(m, idx);
            result_Q.push(item_Q.pop(idx));
        }
        result_Q.print_queue();
    }
}