[백준/BOJ] 1158번 요세푸스 (C++)

www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

문제 분류는 큐를 이용하라고 되어있었지만, 저는 삭제 작업에 유리한 리스트 자료구조를 이용하여 문제를 해결했습니다. 리스트에 1번부터 n번까지 값을 넣고, 리스트가 빌 때까지 k - 1번마다 현재 이터레이터가 가리키는 원소를 벡터에 넣고 그 값을 삭제하는 과정을 반복하면 됩니다.

 

#include <iostream>
#include <vector>
#include <list>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;
    list<int> li;
    vector<int> v;
    for(int i = 1; i <= n; i++) {
        li.push_back(i);
    }
    
    list<int>::iterator it = li.begin();
    while(!li.empty()) {
        for(int i = 0; i < k - 1; i++) {
            if(it == li.end()) it = li.begin();
            it++;
            if(it == li.end()) it = li.begin();
        }
        v.push_back(*it);
        it = li.erase(it); // 삭제 후 시작할 인덱스 번호 갱신 
    }
    
    cout << "<";
    for(int i = 0; i < n - 1; i++) {
        cout << v[i] << ", ";
    }
    cout << v[n - 1] << ">";
}