[백준] 2164 카드2 - 큐

[ 문제링크 ]

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

 

🚩 조건

1. 입력으로 N을 받음. 1<=N<=500,000
2. N장의 카드가 있고, 1번이 제일 위에 위치하고 차례대로 정렬되어 있음.
3. 카드가 한 장 남을 때까지 다음과 같은 동작을 반복함. "우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다."
4. 가장 마지막에 남게 되는 카드를 구해라.

 

 

🚩 접근

2 -> N이 주어지고 1부터 차례대로 push한다고 하면, 선입선출이므로 queue로 구현하자

 

 

🚩 시행착오

구현은 쉽다. 그치만 queue의 메소드들을 헷갈리지 말자.

// 은근 헷갈리는 메소드들..

queue.push_back();	// X
queue.push();	// O

queue.pop();	// O

queue.top();	// X
queue.front();	// O

 

💻 코드 (C++)

#include <iostream>
#include <queue>
using namespace std;

queue<int> q;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        q.push(i);
    }
    while (q.size() > 1) {
        q.pop();

        int top = q.front();
        if (q.size() == 1) {
            break;
        }
        else {
            q.pop();
            q.push(top);
        }
    }
    cout << q.front();
}