카드2 — 큐로 그대로 시뮬레이션(O(n))

아이디어

• 1..n을 큐에 넣고, 맨 앞 버림 → 다음 카드 맨 뒤로 이동을 반복.
• 큐 연산(pop, push, front)은 모두 O(1) → 전체 O(n).

알고리즘

1. 1..n을 큐에 삽입

2. 큐 크기 > 1 동안:

   • 맨 앞 카드 pop() (버림)
   • 그다음 카드 값을 push(front())로 뒤에 붙이고 pop() (앞에서 제거)

3. 남은 한 장 출력

복잡도

• 시간: O(n)
• 공간: O(n)

코드

#include <bits/stdc++.h>
using namespace std;

int n;
queue<int> q;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    int m = n;
    int i = 1;

    while (m--) {
        q.push(i++);
    }

    while (q.size() > 1) {
        q.pop();
        q.push(q.front());
        q.pop();
    }

    cout << q.front();

    return 0;
}

메모

• 입력이 커도 큐 연산은 상수 시간이라 1초 제한에서 안전