1158 요세푸스 문제

STL_list 이용

• list의 begin과 end를 연결
• iterator(반복자)가 이용하여 원형의 형태로 순환하는 포인터의 모습을 가지게 함

int t, k;
    cin >> t >> k;

    list<int> L;

    for(int i=1;i<=t;i++) L.push_back(i);
    cout << '<';

    list<int>::iterator it = L.begin();
    while(L.size() != 1){
        
        for(int i=0;i<k-1;i++){
            it++;
            if(it == L.end())
                it = L.begin();
        }
        cout << *it << ", ";
        it = L.erase(it); // erase 함수의 반환값이 삭제 원소 
        if(it == L.end())
            it = L.begin(); // 끝의 요소 다음이 list.end()인 경우
    }
    cout << *it << '>' << '\n';

STL_vector 이용

• 바킹독 강의에서 말하였듯이 nxt, pre 포인터를 이용하여 배열형태
• 실질적으로 nxt와 pre를 연결하는 링크드 큐의 형태
• 출력값은 가변길의 vector 자료구조를 이용하여서 출력 형태의 편의성을 제공

  int n,k, len = 0;
    cin >> n >> k;

    vector<int> v;

    for(int i=1;i<=n;i++){ // 인덱스를 1부터 시작해야 cursor 값이 완성 됨.
        pre[i] = (i==1)?n:i-1;
        nxt[i] = (i==n)?1:i+1;
        len++;
    }

    int i = 1;
    for(int cur = 1; len !=0; cur = nxt[cur]){
        if(i == k){
            pre[nxt[cur]] = pre[cur];
            nxt[pre[cur]] = nxt[cur];
            v.push_back(cur);
            len--;
            i = 1;
        }
        else i++;
    }
    cout << '<';
    for(size_t i = 0;i < v.size(); i++){
        cout << v[i];
        if(i != v.size() - 1) cout << ", ";
    }
    cout << '>';

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x04/solutions/1158.cpp 참고하였음.