[백준] 요세푸스 문제 1158

문제

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

입력

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

출력

예제와 같이 요세푸스 순열을 출력한다.
<3, 6, 2, 7, 5, 1, 4>

풀이

풀이 1

#include <iostream>
#include <list>

using namespace std;
//리스트 출력하는 함수
void printList(list<int> L){
    for(auto c:L){
        cout << c <<' ';
    }
    cout << "\n";
}

int main()
{
    //1. N, K 입력받기
    int n, k;
    
    cin >>n >> k;
    
    //2. N개의 수를 연결리스트에 넣기
    list<int> L; 
    for(int i=1; i<=n; i++){
        L.push_back(i);
    }
    
    printList(L); // 1 2 3 4 5 6 7
    
    auto cursor = L.begin();
    //3. k번째 위치 맞추기
    for(int i=1; i<k; i++){
        cursor++; //k번만큼 뒤로 이동
    }
    
    cout << "cursor: ";
    cout << *cursor <<'\n';
    
    //4. 리스트에서 k번째 원소 삭제
    list<int> R;
    while(n--){
        R.push_back(*cursor);
        cursor = L.erase(cursor);
        
        cout << "R: ";
        printList(R);
        
        cout << "L: ";
        printList(L);
        
    }
    
    cout << '<';
    for(auto c:R){
        cout << c <<", ";
    }
    cout << '>';
    
   
    return 0;
}

3 6 2 7 이런식으로 삭제가 된 부분에서부터 K번째 수가 삭제되어야 하는데 3번 이후로 cursor가 정적으로 1개씩 늘어나 3 4 5 6 이렇게 삭제가 된다.
1 2 6

풀이 2

#include <iostream>
#include <list>

using namespace std;
//리스트 출력하는 함수
void printList(list<int> L){
    for(auto c:L){
        cout << c <<' ';
    }
    cout << "\n";
}

int main()
{
    //1. N, K 입력받기
    int n, k;
    
    cin >>n >> k;
    
    //2. N개의 수를 연결리스트에 넣기
    list<int> L; 
    for(int i=1; i<=n; i++){
        L.push_back(i);
    }
    
    printList(L); // 1 2 3 4 5 6 7
    
    auto cursor = L.begin();
    //3. k번째 위치 맞추기
    for(int i=1; i<k; i++){
        cursor++; //k번만큼 뒤로 이동
    }
    
    cout << "cursor: ";
    cout << *cursor <<'\n';
    
    //4. 리스트에서 k번째 원소 삭제
    list<int> R;
    while(n--){
        R.push_back(*cursor);
        cursor = L.erase(cursor); //4, 1 2 4 5 6 7
        //새로 넣은 부분
        for(int i=1; i<k; i++){
            cursor++; //k번만큼 뒤로 이동
        }
    
        
        cout << "R: ";
        printList(R);
        
        cout << "L: ";
        printList(L);
        
    }
    
    cout << '<';
    for(auto c:R){
        cout << c <<", ";
    }
    cout << '>';
    
   
    return 0;
}

커서의 위치를 맞춰주기 위해서 이 부분을 새로 넣었다.

for(int i=1; i<k; i++){
   	cursor++; //k번만큼 뒤로 이동
}

그런데 3 6 이후 커서가 2가 아닌 1을 가리키고 있다.

풀이 3

큐를 이용한 풀이

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    int n, k;
    
    cin >> n>>k;
    
    queue<int> Q;
    
    for(int i=1; i<=n; i++) Q.push(i); //1 2 3 4 5 6 7
    
    cout << '<';
    
    while(!Q.empty()){
        //큐를 컨베이어 벨트처럼 돌리기
        for(int i=0; i<k-1; i++){
            Q.push(Q.front());
            Q.pop();
        }
        cout << Q.front();
        Q.pop(); //맨 앞의 원소 삭제
        if(Q.size()) cout<<", ";
    }
    
    cout << '>';
    
    return 0;
}

큐를 이용해서 컨베이어 벨트처럼 k번 맨 앞의 원소를 꺼내서 맨뒤에 넣고, 순서가 되면 front를 통해 맨 앞의 원소를 꺼내서 출력한다. 이렇게 하면 인덱스를 통한 접근을 하지 않아도 되어서 훨씬 편하다