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

이 문제는 #2161 문제와 같은 구조로 푸셔도 되는 문제입니다.  최종 카드를 알아내기 위한 것입니다.  만약 N이 커진다면, 나머지 연산을 통해서 결과를 얻어야 하겠지만, 여기서는 신경쓰지 않아도 됩니다.

 

queue

 

문제의 링크는 다음과 같습니다.

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

2164번: 카드2

 

이 문제와 푸는 방법이 비슷한 #2161 카드 1 문제의 링크는 다음과 같습니다.

https://sdev.tistory.com/1218

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

 

이번 문제는 $N\le 500,000$이지만, 큐를 사용해도  $O(N)$ 알고리즘이기 때문에 크게 문제될 것은 없습니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2164
//        - by Aubrey Choi
//        - created at 2019-07-03
//------------------------------------------------
#include <stdio.h>
#include <queue>

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