[개쉬운 풀이] 백준 11866 요세푸스 문제 0

 

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

 

 

문제

요세푸스 문제는 다음과 같다.

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

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

 

생각

---

1. 처음에는 원형 테이블이니까 vector를 통해서 index+k % n방법으로 접근하려고 했습니다. 그러나 타겟이 매번 제거되면 벡터의 크기가 달라지기 때문에 인덱스 접근방법은 포기했습니다.

2. 다음 vector에서 erase() 함수를 사용하려고 했지만 너무 느릴거 같아서 포기했습니다.

3. 따라서 queue를 이용하여 pop()함수를 통해 풀어보았습니다
* queue의 pop() 함수의 시간복잡도는 0(1) 입니다.
* vector의 erase()함수의 시간복잡도는 0(n)입니다.

풀이

---

1. queue를 통해서 n 번의 숫자들을 init 했습니다.
3. 이후 count 변수를 생성하여 pop()할때마다 count를 1씩 증가하였습니다.
4. count가 k번째에 도달하게 되면 pop한 것을 다시 push() 하지 않고 vector에 저장하였습니다.
5. 이후 count를 다시 초기화 하였습니다.
6. ** 출력형식이 매우 귀찮게 되어있어서 print()함수를 통해 출력형식을 만들어 주었습니다.

 

 

코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

#define endl '\n'

using namespace std;

int n,k;

void input(){
    cin >> n >> k;
}

void print(vector<int> v){
    cout << "<";
    for(int i = 0; i < v.size()-1; i++){
        cout << v[i] << ", ";
    }
    cout << v[v.size()-1] << ">";
}

void sol(){
    queue<int> q;
    vector<int> v;
    //init
    for(int i = 1; i <= n; i++){
        q.push(i);
    }

    int count = 0;
    //k번째 올때 마다 pop할 예정
    //시간제한이 2초이므로 구현형식으로 해결하면 됨
    while(!q.empty()){
        count++;
        int tmp = q.front();
        q.pop();
        if(count != k){
            q.push(tmp);
        }
        else{
            v.push_back(tmp);
            count = 0;
        }
    }

    print(v);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    input();
    sol();
    return 0;
}