[백준/C++] 11866번 요세푸스 문제 0

---

#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    int N, M;
    int start = 0;
    cin >> N >> M;
    vector<int> arr(N);
    vector<int> answer;
    for(int i = 1; i <= N; i++) {
        arr[i-1] = i;
    }

    for(int i = 0; i < N; i++) {
        start += M-1;
        while(start > arr.size()-1) start -= (arr.size());
        answer.push_back(arr[start]);
        arr.erase(arr.begin() + start);
    }
    
    for(int it : arr) {
        answer.push_back(it);
    }
    cout << "<";
    for(int i = 0; i < answer.size(); i++) {
        cout << answer[i];
        i == answer.size()-1 ? cout << ">" : cout << ", ";
    }
}

---

생각 없이 벡터로 풀었는데 생각해보니 Queue를 사용하면 더 빠르게 해결할 수 있다.

입력한 크기만큼 벡터에 값을 채워놓고 인덱스 값으로 원하는 값에 접근해서 뒤에 넣고 그 값을 erase하는 방법을 생각했습니다.

 

코드는 circular queue (원형 큐)를 생각하며 값이 최대 사이즈를 넘어가면 처음으로 돌아가도록 구현하였는데 생각해보면 그냥 queue로 계산된 값이 나올 때까지 빼고 넣고를 반복하고 원하는 값이 나오면 빼는 것으로 구현하는게 더 간단하고 빨랐을 것 같습니다.

---

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

11866번: 요세푸스 문제 0