45. 공주 구하기 (조세퍼스)

나의정답.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

class Node {
public:
    int data;
    Node *Next;
    Node* Prev;
};

class LinkedList {
public:
     Node *Head = NULL;
     Node *Tail = NULL;
     int Count = 0;

     Node* AddLast(int data) {
         Node *newRoom = new Node();
         newRoom->data = data;

         // 첫 번째 노드가 없다면 새로 추가한 노드가 첫번째 노드가 됨.
         if (Head == NULL)
         {
             Head = newRoom;
             Head->Next = newRoom;
             Head->Prev = newRoom;
         }


         // 기존의 마지막 노드와 새로 추가되는 노드를 연결해줌
         if (Tail != NULL)
         {
             Tail->Next = newRoom;
             newRoom->Prev = Tail;
             newRoom->Next = Head;
         }
         Tail = newRoom;
         Count++;
         return newRoom;
     }

     void Remove(Node* room)
     {
         // 기존의 첫 번째 노드의 다음 노드를 첫 번째 노드로 인정
         if (Head == room) {
             Head = Head->Next;
             Tail->Next = Head;
         }
             

         // 기존의 마지막 노드의 이전 노드를 마지막 노드로 인정한다.
         if (Tail == room)
             Tail = Tail->Prev;

         if (room->Prev != NULL)
             room->Prev->Next = room->Next;

         if (room->Next != NULL)
             room->Next->Prev = room->Prev;

         Count--;
     }
};

int main(int argc, char** argv) {
	//freopen("input.txt", "rt", stdin);
    int n, k, i;
    cin >> n >> k;
    LinkedList* a = new LinkedList();
    Node* curr;

    for (i = 0; i < n; i++) {
        a->AddLast(i + 1);
    }

    i = 1;
    curr = a->Head;
    while (a->Count > 1) {
        curr = curr->Next;
        i++;
        
        if (i >= k ) {
            a->Remove(curr);
            curr = curr->Next;
            i = 1;
        }
    }

    cout << a->Tail->data;     
    
    delete a;
    delete curr;
}

입력

8 3

 

로직

curr->data : 1 2 [3] 4 5 [6] 7 8 [1] 2 4 [5] 7 8 [2] 4 7 [8] 4 7 [4] 7
i              : 1 2 [3] 1 2 [3] 1 2 [3] 1 2 [3] 1 2 [3] 1 2 [3] 1 2 [3]
a->Count  : 8 8 [7] 7 7 [6] 6 6 [5] 5 5 [4] 4 4 [3] 3 3 [2] 2 2 [1] 

 

결과

7