[공부] 백준 2164 카드2 C++

📝 문제

• 백준 2164 카드2
  • https://www.acmicpc.net/problem/2164

---

🔍 문제 상황

---

💡 해결 방법 / 접근 방식

• 우선, 카드를 n장 저장 후 맨 위의 카드를 버리고, 그다음 카드를 맨뒤로 보내는 식으로 진행을 해나가는 문제이기에
• queue보다는 vector를 먼저 생각하고 풀이를 진행했습니다.
• 하지만 그결과 erase()로 원소 삭제시, 내부적으로 뒤에 있는 요소들을 모두 한칸씩 이동시켜서 시간 복잡도가 O(n^2) 증가하여 시간초과 발생되는 것을 파악하여, pop push로 원소를 삽입 및 삭제가 가능한 queue를 사용하여 문제를 풀어나갔습니다.

큐(queue)

• 큐는 FIFO(First-In-First-Out) 즉, 선입선출 구조를 따르는 자료구조입니다.
• pop()
  • 입력(삽입): 뒤쪽(Back)에서 넣습니다.
• push()
  • 출력(삭제): 앞쪽(Front)에서 꺼냅니다.
• front()
  • 참조: 제일 앞에 있는 값 확인합니다.

방식	시간 복잡도	삭제 방식	추천 여부
vector.erase(v.begin())	❌ O(n²)	앞 요소 직접 삭제	❌ 시간 초과 발생, 비추천
deque	✅ O(n)	pop_front() 사용	✅ 적극 추천
queue	✅ O(n)	pop() (front만 사용)	✅ 추천

접근 방식

• 위에서 얘기하였듯 vector.erase()를 사용시 요소들을 순차 이동 시켜 시간 초과가 나므로 queue 혹은 deque를 사용하는 것이 바람직하며,
• queue만을 사용해도 충분하기에 queue를 사용하여 풀이를 진행하였습니다.

---

🛠️ 구현 코드

// vector에서 erase로 원소 삭제시, 내부적으로 뒤에 있는 요소들을 모두 한칸씩 이동시켜서 시간 복잡도가 O(n^2) 증가하여 시간초과 발생됨
// vector로 풀 수도 있지만 queue를 통해서 pop push를 진행하는 것이 더 좋음
#include <iostream>
#include <queue>
using namespace std;

int n;
queue<int> q;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        q.push(i + 1); // 1, 2, 3, 4, ... n까지 순서대로 push
    }
    while (q.size() > 1) {
        q.pop(); // 맨 위 카드 pop으로 버림(뺴내기)
        q.push(q.front()); // 그 다음 카드를 맨 아래로 push
        q.pop(); // 그다음 카드도 앞에서 제거(빼내기)
    }
    cout << q.front();
    return 0;
}

🧷 결론

• queue에 대한 이해가 있다면 쉽게 풀 수 있습니다.