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

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

 

조세퍼스 순열이라고도 하며 요세푸스 순열이라고도 부른다.

해당 순열의 정의는 다음과 같다. 출처는 위키피디아이다.

 

전산학이나 수학에서 요세푸스 문제(Josephus problem) 혹은 요세푸스 순열(Josephus permutation)은 다음과 같이 정의한다.

n과 k가 자연수이고, k < n이라고 가정한다. n명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 나가서 k번째 사람을 모임에서 제외한다. 남은 n-1명에서 다시 다음 사람부터 순서를 세서 k번째 사람을 모임에서 제외한다. 이것을 아무도 남지 않을 때까지 계속해서 반복한다. 이때 모임에서 제외되는 사람의 순서를 (n, k) 요세푸스 순열이라고 하며 마지막으로 제외되는 사람을 구하는 문제를 요세푸스 문제라고 한다.

예를 들어 (7,3) 요세푸스 순열은 {3,6,2,7,5,1,4}이며 4번째 위치한 사람이 마지막으로 제외되게 된다.

이 순열은 역사가 요세푸스가 겪은 일화에서 유래하였다.

 

각각의 사람에 대해서 총 N번 순회를 하고 제거를 해야하므로 시간복잡도는 O(NM)이 된다.

다음 문제는 큐를 이용하면 쉽게 풀 수 있다.

다음과 같이 M-1번 pop을 하고 M-1번 push를 하면 그림의 3번째 상태가 된다. (맨 앞의 자료를 pop한 뒤 맨 뒤로 push)

이 상태에서 3이 지목당했으므로 3을 pop을 하게 되면 마지막 형태의 큐가 남아있다.

이 규칙을 계속해서 반복하면 순열 (3,6,2,7,5,1,4)가 나온다. 

총  M-1 +1번의 pop을 하고 M-1번의 push를 하는 꼴이다.

 

생각보다 엄청 쉬운 문제이므로 바로 소스코드를 공개한다.

 

 

#include <iostream>
#include <queue>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    int N, M;
    queue<int> q;
 
    cin >> N >> M;
 
    //initial queue
    for (int i = 1; i <= N; i++)
        q.push(i);
 
    //operation and print
    cout << "<";
    while (q.size()) {
        if (q.size() == 1) //the last one
        {
            cout << q.front() << ">";
            q.pop();
            break;
        }
        for (int i = 1; i < M; i++) {
            q.push(q.front());
            q.pop();
        }
        cout << q.front() << ", ";
        q.pop();
    }
    cout << endl;
    return 0;
}

 

 

[2019.08.08]

2019/08/08 - [PS/알고스팟 문제풀이] - [알고스팟 JOSEPHUS] 조세푸스 문제 (조세퍼스)

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

알고스팟에서 동일한 문제를 풀면서 큐 말고 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);

    LinkedList ll;
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        ll.insertNode(i);
    }
    ll.makeCircular();
    
    cout << "<";
    
    Node * cur = ll.getHead();
    while(ll.getSize()){
        for(int i = 1; i < k; i++)
            cur = cur->next;
        if(ll.getSize() == 1){
            cout << cur->val << ">\n";
            break;
        }
        else    cout << cur->val << ", ";
            
        cur = ll.deleteNode(cur);
    }
    
    return 0;
}