[백준] 2164번: 카드2 | C++ 풀이

# 문제

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

 

 

---

 

# 풀이

'우선, 제일 위에 있는 카드를 바닥에 버린다'에서 우리는 queue를 사용해 푸는 문제라는 걸 파악할 수 있다.

바로 정답 소스코드를 확인해보자.

 

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

int main(){
    int n;
    cin >> n;
    queue<int> set;
    for(int i=1; i<=n; i++){
        set.push(i);
    }

    while(set.size() != 1){
        set.pop();
        set.push(set.front());
        set.pop();
    }
    
    cout << set.front();
    return 0;
}

큐의 개념만 알고 있다면 간단한 문제다.

1~N까지의 카드 번호를 push() 함수를 통해 큐에 넣어준다. 예시의 경우 for문을 돌고 나면 {1, 2, 3, 4, 5, 6} 이 된다.

그 다음엔 카드가 한 장 남을 때까지 while문을 돌려준 후 큐에 남은 하나의 카드를 출력하면 끝인데 while문 안에서는 아래와 같은 과정이 반복된다.

 

우선 큐는 FIFO 구조를 따른다. 따라서 원소를 제거하는 pop() 함수를 사용하면 가장 앞에 있는 (예시에서는 1) 원소가 삭제되므로, 문제에서 원하는 방식으로 동작시킬 수 있다. 그 다음에 위치한 카드는 가장 아래로 옮겨야 하므로 front() 함수를 통해 찾은 가장 앞에 있는 원소를 push()를 통해 뒤로 밀어 넣어준다. 그 후 앞에 있는 건 pop()을 통해 삭제해주면 정말 끝이다.

큐에 카드(원소)가 하나 남았을 때 while문을 탈출하므로 가장 앞에 있는 원소를 출력해주면 정답!

 

 

 

 

 

 

 

---

 

 

 

2164번: 카드2