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

20 Feb 2018

Reading time ~1 minute

1158

순환 단방향 링크드 리스트를 사용해서 풀면 된다.
시간 복잡도는 N번 반복문을 돌며 M번 참조하는 연산을 하므로 O(NM)인데,
1<=M<=N<=5000 이라는 조건이 주어졌으므로 충분히 풀 수 있다.

공간 복잡도는 O(N)이다.
이 문제를 풀며 역시 리스트는 그림을 그리며 푸는게 최고라는 생각이 들었다..

아래는 소스.

#include <iostream>

using namespace std;

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

class CircleList
{
    Node* head;
    Node* tail;
public:
    void init(int N)
    {
        head = new Node();
        head->value = 1;
        
        tail = head;
        for(int i=2;i<=N;i++)
        {
            Node* n = new Node();
        
            n->value = i;
            tail->next = n;
            tail = tail->next;
        }
        
        tail->next = head;
    }
    int pop(int M)
    {
        for(int i=0;i<M-1;i++)
        {
            tail = tail->next;
            head = head->next;
        }
        
        int ret_value = head->value;
        
        Node* t = head;
        
        tail->next = head->next;
        head = head->next;
        delete t;
        
        return ret_value;
    }
};
int main()
{
    CircleList cl;
    
    int M,N;
    
    cin>>N>>M;
    
    cl.init(N);
    
    cout<<"<";
    while(N--)
    {
        cout<<cl.pop(M);
        if(N != 0)
            cout<<", ";
    }
    
    cout<<">"<<endl;
    
    return 0;
}

algorithm