[알고스팟 JOSEPHUS] 조세푸스 문제 (조세퍼스)

 

 

문제 : https://algospot.com/judge/problem/read/JOSEPHUS

algospot.com :: JOSEPHUS

---

 

백준 1158 번 조세퍼스 순열 문제와 비슷한 맥락.

2018/03/28 - [PS/백준 문제풀이] - [백준 1158] 조세퍼스 순열 문제

[백준 1158] 조세퍼스 순열 문제

하지만 이번에는 N, K 값이 1000으로 더 작기 때문에 직접 circular linked list를 만들어 풀었다.

 

#include <iostream>
#include <list>
using namespace std;

int n, k;
struct Node{
    int val;
    Node *next, *prev;
};

class LinkedList{
private:
    int size;
    Node *head, *tail;
public:
    LinkedList(){
        head = NULL;
        size = 0;
    }
    
    void insertNode(int v){
        Node *cur = new Node;
        cur->val = v;
        size++;
        
        if(!head) head = tail = cur;
        else{
            cur->prev = tail;
            tail->next = cur;
            tail = cur;
        }
    }
    
    int getSize(){
        return size;
    }
    
    // 머리랑 꼬리 이어줌!
    void makeCircular(){
        head->prev = tail;
        tail->next = head;
    }
    
    // 현재 노드 삭제 후 다음 노드 리턴.
    Node* deleteNode(Node *cur){
        Node* nextNode = cur->next;
        cur->prev->next = cur->next;
        cur->next->prev = cur->prev;
        delete cur;
        size--;
        return nextNode;
    }
    
    Node* getHead(){
        return head;
    }
    
    // 귀찮아서 남아있는 애 둘 그냥 출력.
    void printRemains(Node* cur){
        if(cur->val > cur->next->val){
            cout << cur->next->val << " " << cur->val << '\n';
        }else{
            cout << cur->val << " " << cur->next->val << '\n';
        }
        delete cur->next;
        delete cur;
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--){
        LinkedList ll;
        cin >> n >> k;
        for(int i = 1; i <= n; i++){
            ll.insertNode(i);
        }
        ll.makeCircular();
        
        Node * cur = ll.getHead();
        while(ll.getSize() > 2){
            cur = ll.deleteNode(cur);
            for(int i = 1; i < k; i++)
                cur = cur->next;
        }
        
        ll.printRemains(cur);

    }
    return 0;
}