#1158. 요세푸스 문제

알고리즘

큐를 이용하여 문제를 풀었다. 먼저 1부터 N까지의 수를 큐에 삽입한다. 이후 K-1번만큼 큐의 맨 앞 수를 빼서 맨 뒤에 삽입한다. 그럼 이제 큐의 맨 앞 수가 K번째 수이기 때문에 그 수를 제거하고 출력한다. 이 과정을 N-1번 반복한다. 마지막 수는 쉼표 없이 출력해주기 위해 마지막에 따로 출력해 줄 것이다.

c++

int main() {

    queue<int> q;
    
    int n, k;
    cin >> n >> k;
    
    // 1부터 n까지의 수를 큐에 삽입한다
    for(int i=1; i<n+1; i++) {
        q.push(i);
    }
    
    // '<' 출력
    cout << "<";
    
    // n-1번 만큼 반복한다 (마지막 수는 따로 출력해주기 위해)
    n--;
    while(n--) {
        
        // k-1번만큼 큐의 맨 앞 수를 빼서 맨 뒤에 삽입한다
        for(int i=0; i<k-1; i++){
            q.push(q.front());
            q.pop();
        }
        
        // 큐의 맨 앞 수를 제거하고, 그 수를 출력한다 (=k번째)
        cout << q.front() << ", ";
        q.pop();
    }
    
    // 큐의 맨 앞 수를 출력한다 (마지막에 남은 수)
    cout << q.front();
    cout << ">";
}