[백준/C++] 2164번: 카드2 - Vector의 함정과 Queue의 효율성

1. 문제 정보

• 문제 번호: 2164번
• 문제 이름: 카드2

 

• 문제 요약:
  1. 가장 위에 있는 카드를 버린다.
  2. 그다음 가장 위에 있는 카드를 가장 아래로 옮긴다.
  3. 마지막에 남게 되는 카드의 번호를 구하라.

 

2. 접근 방법 (알고리즘)

 

❌ 첫 번째 시도: Vector 사용 (시간 초과)

가장 먼저 떠오르는 방식은 vector를 사용하는 것이다. 하지만 이 방식은 치명적인 성능 문제가 있다.

• 원인: vector::erase(cards.begin()) 때문이다.
• 동작 원리: vector는 데이터가 메모리에 연속적으로 배치되어 있다. 따라서 첫 번째 원소를 지우면, 뒤에 있는 모든 원소를 앞으로 한 칸씩 당겨오는 재배치 작업이 발생한다.
• 시간 복잡도: 한 번 지울 때 O(N)이 걸린다. 이를 $N$번 반복하므로 전체 복잡도는 $O(N^2)이다. N이 500,000일 경우 약 2,500억 번의 연산이 필요하여 무조건 시간 초과가 발생한다.

 

✅ 최종 접근: Queue 사용 (성공)

이 문제처럼 "앞에서 빼고 뒤로 넣는" 동작(First-In, First-Out)에 최적화된 자료구조는 Queue(큐)이다.

• 동작 원리: std::queue는 앞부분에서 원소를 제거(pop)하거나 뒷부분에 추가(push)하는 동작이 O(1)에 수행되도록 설계되어 있다.
• 시간 복잡도: 전체 과정을 N번 반복해도 O(N)으로 끝난다.

 

3. 코드 구현 (정답)

#include <iostream>
#include <queue> // queue 자료구조 사용

using namespace std;

int main() {
    // 입출력 최적화
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    queue<int> q;

    // 1부터 N까지 카드를 큐에 삽입
    for (int i = 1; i <= n; i++) {
        q.push(i);
    }

    // 카드가 한 장 남을 때까지 반복
    while (q.size() > 1) {
        // 1. 가장 위의 카드를 버림
        q.pop();

        // 2. 그다음 카드를 맨 뒤로 보냄
        int front_card = q.front();
        q.push(front_card);
        q.pop();
    }

    // 마지막 남은 카드 출력
    cout << q.front() << "\n";

    return 0;
}

---

4. 배운 점 & 회고 (TIL) ✍️

① 자료구조마다 '비싼' 연산이 다르다

vector는 인덱스로 접근하는 속도(O(1))는 매우 빠르지만, 앞부분에 데이터를 추가하거나 삭제하는 것은 매우 비싼(O(N)) 작업이다. 반면 queue나 deque는 양 끝단에서의 조작에 특화되어 있다. 문제를 읽고 "앞에서 제거하고 뒤로 넣는다"는 흐름이 보이면 바로 queue를 떠올려야 한다는 것을 배웠다.

② vector::erase의 내부 동작

데이터가 메모리에 연속적으로 붙어 있다는 특징은 캐시 효율성 면에서는 좋지만, 중간이나 앞부분의 데이터를 삭제할 때 발생하는 '도미노 현상'(데이터 시프팅)을 항상 경계해야 한다.

③ Queue의 주요 함수 정리

함수	설명	시간 복잡도
push(x)	뒤(back)에 데이터 삽입	$O(1)$
pop()	앞(front)의 데이터 삭제	$O(1)$
front()	가장 앞의 데이터 참조	$O(1)$
back()	가장 뒤의 데이터 참조	$O(1)$
size()	큐에 담긴 원소 개수 반환	$O(1)$

단순히 기능을 구현하는 것을 넘어, 자료구조의 내부 구현 방식이 성능에 어떤 차이를 만드는지 다시 한번 체감할 수 있는 문제였다. 앞으로는 데이터의 삽입과 삭제가 빈번한 위치가 어디인지 먼저 파악하는 습관을 들여야겠다.

---

다음 공부 목표:

std::queue와 유사하지만 앞뒤 양방향에서 삽입/삭제가 가능한 std::deque에 대해서도 정리해 볼 예정이다.