[백준 1158번] 조세퍼스 문제

link : https://www.acmicpc.net/problem/1158

조세퍼스 문제 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	10534	5209	4036	51.763%

문제

조세퍼스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 M(≤ N)이 주어진다. 이제 순서대로 M번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, M)-조세퍼스 순열이라고 한다. 예를 들어 (7, 3)-조세퍼스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 M이 주어지면 (N,M)-조세퍼스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ M ≤ N ≤ 5,000)

출력

예제와 같이 조세퍼스 순열을 출력한다.

예제 입력 1 

7 3

예제 출력 1 

<3, 6, 2, 7, 5, 1, 4>

** 이번 문제는 공부하면서 만든 STL을 실험하면서 해결한 문제입니다. 이 코드의 효율성은 매우 떨어집니다! **

모 기업 코딩 테스트에서 나온 문제와 같은 문제였다. 그때는 지금처럼 리스트를 사용하지 않고, 배열로 만들어서

최대한 빠른 시간 안에 문제가 해결되도록 해서 풀었었다. 지금은 리스트를 공부하고 있기 때문에 리스트를 제작해서 풀었다! (원형 리스트)

#include<iostream>
 
using namespace std;
 
template <typename T>
class LinkedList {
private:
    class Node {
 
    public:
        T data;
        Node* nextNode;
    };
 
    void valid(int);
    int size;
    Node *Head = new Node;
    Node *cur;
 
public:
    LinkedList();
    ~LinkedList();
    T get_data(int);
    bool isEmpty();
    int get_size();
    void insert(T);
    void insert(T, int);
    void change(T, int);
    void remove(int);
};
 
template<typename T>
LinkedList<T>::LinkedList() {
    Head->data = NULL;
    Head->nextNode = NULL;
    LinkedList::size = 0;
}
 
template<typename T>
LinkedList<T>::~LinkedList() {    
    Node *t = Head;
    Node *de = Head;
 
    for (int i = 0; i < LinkedList::size; i++) {
        t = t->nextNode;
        delete de;
        de = t;
    }
}
 
template<typename T>
void LinkedList<T>::valid(int Count) {
    if (Count > LinkedList::size) {
        throw "Error : 유효하지 않은 index입니다.";
    }
}
 
template<typename T>
bool LinkedList<T>::isEmpty() {
    return size > 0 ? false : true;
}
 
template<typename T>
int LinkedList<T>::get_size() {
    return size;
}
 
template<typename T>
T LinkedList<T>::get_data(int index) {
    Node* temp = cur;
    for (int i = 0; i < index; i++) {
        temp = temp->nextNode;
    }
 
    return temp->data;
}
 
template<typename T>
void LinkedList<T>::insert(T data) {
    Node * NewNode = new Node;
    NewNode->data = data;
    NewNode->nextNode = NULL;
 
    if (Head->data == NULL) {
        Head = NewNode;
        Head->nextNode = NewNode;
        cur = Head;
    }
    else if (Head->nextNode == NULL) {
        Head->nextNode = NewNode;
        NewNode->nextNode = Head;
    }
    else {
        Node* temp = Head;
        for (int i = 0; i < LinkedList::size - 1; i++) {
            temp = temp->nextNode;
        }
        temp->nextNode = NewNode;
        NewNode->nextNode = Head;
    }
 
    LinkedList::size++;
}
 
template<typename T>
void LinkedList<T>::insert(T data, int index) {
    try {
        valid(index);
    }
    catch (const char* msg) {
        cout << msg << endl;
        return;
    }
 
    Node * NewNode = new Node;
    NewNode->data = data;
    NewNode->nextNode = NULL;
 
    if (Head->data == NULL) {
        Head = NewNode;
        Head->nextNode = NewNode;
    }
    else if (Head->nextNode == NULL) {
        Head->nextNode = NewNode;
        NewNode->nextNode = Head;
    }
    else {
        Node* temp = Head;
        for (int i = 0; i < index - 1; i++) {
            temp = temp->nextNode;
        }
        NewNode->nextNode = temp->nextNode;
        temp->nextNode = NewNode;
 
        if (index == size) {
            NewNode->nextNode = Head;
        }
    }
 
    LinkedList::size++;
}
 
template<typename T>
void LinkedList<T>::change(T data, int index) {
    try {
        valid(index);
    }
    catch (const char* msg) {
        cout << msg << endl;
        return;
    }
 
    Node* temp = LinkedList::Head;
    for (int i = 0; i < index; i++) {
        temp = temp->nextNode;
    }
 
    temp->data = data;
}
 
template<typename T>
void LinkedList<T>::remove(int index) {
 
    Node* temp = cur;
    Node* remove = cur;
 
    if (index == 0) {
        for (int i = 0; i < LinkedList::size-1; i++) {
            temp = temp->nextNode;
        }
    }
 
    else{
        for (int i = 0; i < index - 1; i++) {
            temp = temp->nextNode;
            remove = remove->nextNode;
        }
        remove = remove->nextNode;
    }
 
    temp->nextNode = remove->nextNode;
    cur = temp->nextNode;
 
    if (remove == Head) {
        Head = remove->nextNode;
    }
 
    remove->nextNode = NULL;
    delete remove;
    LinkedList::size--;
}
 
int main() {
 
    LinkedList<int> list;
    int N, M;
 
    cin >> N >> M;
 
    for (int i = 1; i <= N; i++) {
        list.insert(i);
    }
 
    cout << "<";
 
    for (int i = 0; i < N; i++) {
        cout << list.get_data(M - 1);
        if (i != N - 1) cout << ", ";
        list.remove(M - 1);
    }
 
    cout << ">";
 
    return 0;
}