연습문제

숫자가 순서대로 n 크기의 나열된 리스트가 있다.

이를 m만큼 건너 뛰며  제외시킨다고 할 때, 그 제외된 목록들을 순서대로 출력해보자.

 

struct Node
{
    int n;
    Node* before;
    Node* next;
};

int main()
{
    int n = 0;
    int m = 0;
    std::cin >> n >> m;

    std::vector<Node*> v(n);

    for (int i = 0; i < n; ++i)
    {
        v[i] = new Node;
        v[i]->n = i + 1;
    }

    for (int i = 0; i < n; ++i)
    {
        v[i]->before = v[i - 1 >= 0 ? i - 1 : n - 1];
        v[i]->next = v[i +1 < n ? i + 1 : 0];
    }

    int count = 0;
    int remain = n;

    Node* cur = v[0];

    while (remain > 1)
    {
        if (++count == m)
        {
            cout << cur->n << ", ";

            cur->before->next = cur->next;
            cur->next->before = cur->before;

            Node* del = cur;
            cur = cur->before;
            delete del;
            --remain;

            count = 0;
        }

        cur = cur->next;
    }

	return 0;
}