[C/C++] 백준 #2161 카드1(큐 자료구조)

이번 문제는 요세푸스(Josephus) 문제와 아주 유사합니다.  요세푸스 문제는 K번째를 제하는 형태이지만, 이 문제에서는 먼저 제하고 시작하는 것이 좀 다릅니다.  요세푸스 (N, 2) 문제와 비숫합니다.

 

Josephus problem

 

아래는 문제의 링크입니다. 

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

2161번: 카드1

 

이 문제는 큐(queue) 자료구조를 활용해서 할 수 있습니다.  요세푸스 문제는 큐를 단순하게 이용할 경우 (N, K) 요세푸스 문제는 큐의 pop 횟수 기준으로 \(O(NK)\)의 시간 복잡도를 보입니다.  나머지 연산을 사용하면 더 빠르게 처리할 수 있지만, K가 2라고 한다면, \(O(N)\) 알고리즘인 셈이므로, 복잡하게 생각하지 않아도 됩니다.  더구나 제하는 카드들을 출력해야 하는 문제이므로, 요세푸스 문제라고 해도 큐를 사용하면 됩니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2161
//        - by Aubrey Choi
//        - created at 2019-06-28
//------------------------------------------------
#include <stdio.h>
#include <queue>

int main()
{
    std::queue<int> queue;
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) queue.push(i);
    while(queue.size() > 1)
    {
        printf("%d ", queue.front());
        queue.pop();
        queue.push(queue.front());
        queue.pop();
    }
    printf("%d", queue.front());
    return 0;
}