BOJ 1158 조세퍼스 문제

BOJ 1158 조세퍼스 문제

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define endl "\n"
typedef struct _NODE{
    int Data;
    _NODE* Prev = NULL;
    _NODE* Next = NULL;
}NODE;

int n, k;

NODE* head = NULL;
void linkedNodes(){
    for(int i = 1; i <= n; i++)
    {
        // 새로 추가한 노드
        NODE* tmp = (NODE*)malloc(sizeof(NODE));
        tmp -> Data = i;
        tmp -> Prev = NULL;
        tmp -> Next = NULL;
        if(head == NULL) // 노드가 아무것도 없을 때
        {
            head = tmp;
        }
        else // 노드가 한개 이상일 때
        {
            NODE* curr = head;
            while(curr -> Next != NULL) // 제일 마지막 노드로 이동 시키기 위함
            {
                curr = curr -> Next;
            }
            curr -> Next = tmp;
            tmp -> Prev = curr;
        }
        if(i == n){ // n개의 노드가 될때, 첫노드(head)와 마지막 노드를 연결시켜주기
            tmp -> Next = head;
            head -> Prev = tmp;
        }
    }
}

void displayLinkes(){
    int cnt = 1;
    int c = 1;
    NODE* curr = head;
    cout <<"<";
    while(curr != NULL)
    {
        NODE* tmp = curr; // 현재 노드를 저장
        if(cnt % k == 0) // k번째의 노드만을 출력 시키기 위함.
        {
            if(c == n) // c를 증가시켜 n개의 개수를 출력시키면 종료하기 위한 조건
            {
                cout << curr -> Data << ">" << endl;
                free(curr);
                return;
            }
            else // 아직 n개를 다 출력하지 못했을 때!
            {
                cout << curr -> Data << ", ";
            }
            curr -> Prev -> Next = curr -> Next; // 현재 노드 삭제 연산
            curr -> Next -> Prev = curr -> Prev;
            free(curr); // 현재 노드 동적 메모리 해제
            curr = tmp; // 쓰레기 값을 보유한 현재 노드에게 첫 시작에 저장한 tmp 노드 대입
            curr = curr -> Next; // 다음 노드로 이동
            c++; // 하나를 출력했으니 증가
        }
        else // k번째 노드가 아닌 경우
        {
            curr = curr -> Next; // 다음 노드로 이동
        }
        cnt++;
    }
}

int main(void){
    cin >> n >> k;
    linkedNodes();
    displayLinkes();
}