11866번: 요세푸스 문제0

먼저 원형 큐를 구현한 뒤 그 안에서 첫번째 자리를 삭제하는 경우와 이 외의 경우로 나누어 풀이를 작성하였다.

 

이 문제를 풀기 전에 큐에 대해 공부한 뒤, 단방향 연결리스트로 큐를 구현이 가능하다면, 

원형 큐를 구현한 뒤 접근하면 매우 쉽게 풀린다.

 

놓친 점 : 첫번째 수를 빼는 경우를 고려하지 않아서 오류가 났었다. 그리하여 경우를 두가지로 나누어 삭제를 진행하였다.

 

또한 삭제의 경우

head = head->next; 와 같이 작성한 적이 많은데 이 경우 메모리 누수가 발생하고 n이 커지면 무수한 손실이 발생하여 delete를 사용하여 꼭 해제해주어야 한다.

#include <iostream>
using namespace std;
struct Node{
    int num;
    Node *next;
};
Node *tail, *head;
int k;
void push(int num)
{
    if(tail == NULL)
    {
        tail = new Node();
        tail->num = num;
        tail->next = tail;
        head = tail;
    }
    else
    {
        Node *temp = new Node();
        temp->num = num;
        temp->next = tail->next;
        tail->next = temp;
        tail = temp;
    }
}
void pop()
{
    if(k == 1)
    {
        Node *temp = head;
        tail->next = tail->next->next;
        cout << temp->num << ", ";
        delete temp;
        
    }
    else
    {
        for(int i=1; i<k-1; i++)
        {
            head = head->next;
        }
        Node *del = new Node();
        del = head->next;
        head->next = head->next->next;
        cout << del->num << ", ";
        delete del;
    }

}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n >> k;
    for(int i=1; i<=n; i++)
        push(i);
    cout << '<';
    while(head->next != head)
    {
        pop();
        head = head->next;
    }
    cout << head->num << '>';
    return 0;
}