[C++] 1158 요세푸스 문제

문제

1158 요세푸스 문제

정답

#include <iostream>
#include <queue>

using namespace std;

vector<int> calculate(queue<int> &q, int k){
    vector<int> ans;
    int count = 0;
    while(!q.empty()){
        int tmp = q.front();
        q.pop();
        if(++count != k){
            q.push(tmp);
        }   
        else{   //제거
            ans.push_back(tmp);
            count = 0;
        }
    }
    return ans;
}

int main()
{
    int n, k;
    cin >> n >> k;
    
    queue<int> q;
    
    for(int i=1; i<=n; i++){
        q.push(i);       
    }
    
    vector<int> ans = calculate(q, k);
    
    //출력
    cout << "<";
    for(int i=0; i<n-1; i++){
        cout << ans[i] << ", ";
    }
    cout << ans[n-1] << ">";
    
    return 0;
}

• queue를 이용하는 간단한 문제

생각의 흐름

사골 같은 문제... 근데 매번 풀때마다 고민하게 되는..

예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

나 몇 년 전에는 이거 무슨 소리인지 몰라서 ㅇㅅㅇa.. 했는데 지금은 단번에 이해가 된다 휴
일단... 걸린 놈을 pop() 해야함. 그리고 남은 사람들에서 다시 제거할 사람을 축출 반복.
vector[1 2 3 4 5 6 7] 에서 몇 번째 사람을 erase
deque[1 2 3 4 5 6 7] 에서 앞에서 빼고 뒤에서 넣길 반복?
아니 이건 queue에서 해도 되잖아.
queue 2개를 두고 옮기고, 빼고를 반복?

2번째가 제일 나아보인다. 근데 나 지금껏 디큐dequeue인줄 앎.. 덱이었네.

• 먼저 1~n까지 큐에 추가하기
• 큐에서 pop()하고 count++
  - count!=k라면 push()
  • else, 축출할 사람이니 answer vector에 추가
• 큐가 빌 때까지 반복

기억하면 좋을 것

//내 코드
    while(!q.empty()){
        int tmp = q.front();
        q.pop();
        if(++count != k){
            q.push(tmp);
        }   
        else{   //제거
            ans.push_back(tmp);
            count = 0;
        }
    }

//우수 코드
    while(!q.empty()) {
        for(int i = 0; i < k-1; i++) { // k-1번 pop & push
            q.push(q.front());
            q.pop();
        }

        // k번째 사람 pop 후 순열에 추가
        result.push_back(q.front());
        q.pop();
    }

나는 pop한 걸 저장하고, 그게 k번째인지 아닌지 매번 검사하는 방향을 취했는데
우수 코드는 애초부터 k-1번째까지 pop과 동시에 push하고, k번째라면 벡터에 추가했다.
매번 검사하는 게 아니니까 시간이 훨씬 줄어든다!
항상 느끼지만 코테 할때는 '매번'이냐, '필요할 때' 검사이냐 생각하는 게 중요한 것 같다.