(ALGORITHM) 백준 1158 문제 - 조세퍼스 문제

시간 복잡도는 N번 반복문을 돌며 M번 참조하는 연산을 하므로 O(NM)
1<=M<=N<=5000 임으로 충분히 작으니 !

공간 복잡도는 O(N)이다.

리스트 문제는 확실히 직접 그려서 푸는게 좋다는 결론을 얻었다.

#include<iostream>

using namespace std;

class Node
{
public:
    Node* next;
    int value;
};

class CircularList
{
    Node* head;
    Node* tail;
    
public:
    CircularList(int N)
    {
        head = new Node();
        head->value = 1;
        
        Node* tmp_Node = head;
        for(int i=2;i<N+1;i++)
        {
            Node *n = new Node();
            n->value = i;
            tmp_Node->next = n;
            tmp_Node = n;
        }
        tail = tmp_Node;
        tail->next=head;

 // 제대로 들어있는지 확인     
//        for(int i=0;i<N*2;i++)
//        {
//            cout<<head->value<<endl;
//            head = head->next;
//        }
    }
    int pop(int M)
    {
        for (int i = 0; i<M-1; i++) {
            head = head->next;
            tail = tail->next;
        }
        
        int rt = head->value;
        
        Node*tmp = head;
        tail->next=head->next;
        head = tail->next;
        delete tmp;
      

        return rt;
    }
};
int main()
{
    
    int N,M;
    cin>>N>>M;
    
    CircularList cl = CircularList(N);
    
    cout<<"<";
    while(N--)
    {
        cout<<cl.pop(M);
        if(N != 0) cout<<", ";
    }
    cout<<">"<<endl;
    return 0;
}