백준 2164번 - 카드2 문제 C++ [Queue]

📍 백준 2164번 - 카드2 문제 C++ [Queue]

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

---

🧩문제 요약

 

<Queue>

숫자 N이 주어질 때 1부터 N까지의 카드가 있다고 가정한다.

다음과 같은 규칙을 따른다고 할때, 제일 마지막에 남는 카드는 무엇인지 출력하라. 

1. 맨위의 카드를 버린다.
2. 맨위 카드를 맨 뒤로 보낸다.

 

---

🧾내가 작성한 초기 코드 

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

int main(){
    int n, arr[500001], i, flag=1, tmp ;
    cin >> n ;
    queue<int> q; 
    for(i=1; i<=n;i++){
        q.push(i);
    }

    while(q.size()!=1){
        if(flag){
            q.pop();
            flag=0;
        }else{
            tmp = q.front();
            q.pop();
            q.push(tmp);
            flag = 1; 
        }        
    }
    cout << q.front() << "\n" ;
}

---

👍이 문제에서 배운점

 

😕 문제점 1. 

배열을 사용하면 카드를 버리고 뒤로 보낼 때마다 shift를 해주던 배열의 인덱스를 가지고 수식을 하던... 엄청 복잡해 진다. 

그래서 배열이 아닌 다른 자료구조를 사용하는 것이 좋을 것 같다. 

 

 

✅ Queue

Queue를 사용하면 FIFO이기 때문에 쉽게 처리가 가능하다. 

나는 1번과 2번 규칙에 따라 동작을 다르게 하기 위해서 flag변수를 사용하였는데 굳이 이렇게 하지 않아도 됐다. 

1번과 2번 규칙을 하나로 본다면 "맨위 카드를 한장 버리고 그다음 카드를 뒤로 보낸다"로 정리할 수 있다. 

그래서 이 행동을 하나로 묶어서 반복을 돌리면 됐다. 

 

그래서 완성된 코드는 아래와 같다. 

 

 

---

🧾 완성된 코드 

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

int main(){
    int n, arr[500001], i, flag=1, tmp ;
    cin >> n ;
    queue<int> q; 
    for(i=1; i<=n;i++){
        q.push(i);
    }

    while(q.size()!=1){
        q.pop();
        q.push(q.front());
        q.pop();
    }
    cout << q.front() << "\n" ;
}