[백준 2164번] 카드2

🔗알고리즘 문제

Queue 자료구조를 응용하는 기초적인 문제로 Queue를 알게 된 후 접하게 되어 손 쉽게 해결 할 수 있었다.

문제 분석

이 문제는 간단하게 1부터 n까지의 숫자가 순서대로 배열에 들어있을 때 배열에 남은 값이 하나 일 때까지 작업을 한 후 마지막 남은 값을 찾는 문제이다.

해야하는 작업은 다음과 같다.

1. 제일 위에 있는 값을 삭제한다.
2. 제일 위에 있는 값을 제일 뒤로 보낸다.

발상

해야하는 작업이 복잡하지 않고 사실상 신경써서 봐야 하는 값은 위에 있는 값이기에 단순한 while문과 queue를 이용하여 구현해보기로 하였다.

알고리즘 설계

1. Queue에 1부터 n까지의 값을 담는다.
2. Queue에 값이 하나 남을 때까지
   Queue를 한번 pop한 후 맨 앞에 값을 맨 뒤로 보낸다.
3. Queue에 남은 값을 출력한다.

코드

#include<iostream>
#include<queue>

using namespace std;

int main(){
    int N;
    queue<int> deck;

    cin >> N;
    for(int i = 1; i <= N; i++){
        deck.push(i);
    }

    while(deck.size() != 1){
        deck.pop();
        int temp = deck.front();
        deck.pop();
        deck.push(temp);
    }

    cout << deck.front();
}