백준 1158 요세푸스 문제 : 큐,벡터로 각각 푸는 2가지 방법

문제 링크

www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

풀이 아이디어

규칙성을 찾아 벡터를 이용해 푸는 방법과

큐를 이용해 직접 k-1번씩 앞에 숫자를 빼서 뒤에넣은 후 k번째 숫자를 출력하는 방법이 있다.

어느것으로 풀어도 상관없음.

코드

방법 1. 큐를 이용해 푸는 법

#include <bits/stdc++.h>
using namespace std;
queue<int> q;
int n,k,temp;
int main(void){
    cin >> n >> k;
    for(int i=1; i<=n;i++) q.push(i);

    cout<<"<";
    while(true){
        for(int i=0; i < k - 1; i++) {
            temp = q.front();
            q.pop();
            q.push(temp);
        }
        cout<<q.front();
        q.pop();
        if(!q.size()) break;
        cout<<", ";
    }
    cout<<">";
}

방법 2. 벡터를 이용해 푸는 법

#include <iostream>
#include <vector>
using namespace std;
int n, m;
vector <int> v;

int main() {
    cin >> n >> m;
    for(int i = 0; i < n; i++) v.push_back(i + 1);
    int pos = 0;
    putchar('<');
    while(!v.empty()) {
        pos = (pos + m - 1) % v.size();
        cout << v[pos];
        v.erase(v.begin() + pos);
        if(v.size() == 0) cout << ">" << "\n";
        else cout << ", ";
    }
    return 0;
}