[ 백준 2161 ] 카드1 (C++)

백준의 카드1(2161) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 이 문제는 주어진 카드에서 1장이 남을 때 까지, 카드를 일정한 조건에 따라 버리면서 버린 순서를 출려갛고 마지막에 남은

   카드를 출력하는 것이 문제이다.

   이런 경우, 배열을 사용해도 좋지만 Queue를 사용하면 굉장히 편한다.

   Queue의 경우, 선입선출 구조로서, 접근은 가장 앞에 있는 원소로만 가능하고, 가장 앞에 있는 원소만 빼낼 수가 있다.

   또, 삽입을 할 경우 자동적으로 가장 마지막으로 삽입되는 선입선출구조이다.

   그렇다면, 이 문제에서 왜 Queue가 편한지 문제에 빗대어서 알아보자.

   이 문제는 "제일 위에 있는 카드를 버리고, 그 다음 제일 위에 있는 카드를 제일이밑으로 옮긴다" 라는 식으로

   카드를 관리하게 된다.

   여기서 제일 위 = Queue의 front사용이 된다.

   카드를 버리는 것 = Queue의 pop 연산에 해당되며,

   제일 밑으로관리긴다 = Queue의 push 연산에 해당된다고 생각하면 굉장히 관리하기가 쉽다.

   Queue에 { 1, 2, 3 } 이라는 원소가 들어있다고 생각해보자.

   여기서 Queue.front() = 1 이며, Queue.pop()을 하게 되면 Queue의 상태는 { 2, 3 } 이 된다.

   그리고, Queue.push(4)를 하게되면 Queue의 상태는 { 2, 3, 4 }가 된다.

   이런식으로 관리할 수가 있다.

   카드가 1장이 남았는지 판단하는 방법은 Queue.size를 사용하면 된다. Queue의 Size가 1이라는 의미는 즉 카드가 한 장

   남았다는 의미가 된다.

2) 본인은 문제를 해결하는 과정에서, 남은 카드들을 저장하는 Vector 하나와, 카드를 관리하는 Queue를 하나 사용했다.

   카드가 1장이 남을 때 까지(Queue의 Size가 1일 때 까지) 무한루프를 통해서 반복을 진행한다.

   예제 입력 1을 통해서 구체적으로 알아보자. 예제 입력 1에서는 7번까지의 카드를 입력으로 준다.

   즉, Queue에 { 1, 2, 3, 4, 5, 6, 7 } 을 push하고 시작한다. 이후 순차적으로 알아보자.

   ( V = Vector, Q = Queue를 의미 )

   1. 제일 위에 있는 카드를 버린다.

   - 버리는 카드를 저장하는 Vector를 하나 사용한다고 하였다. 즉, 제일 위에 있는 카드를 버리는 것이므로

     '1'을 Vector에 저장해줘야한다.

     V.push_back(Q.front())   - 버리는 카드를 저장해주고

     Q.pop()                 - 원래 카드 리스트에서 버려버린다.

   2. 그 다음 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

   - Q.push(Q.front())        - 카드에서 제일 위에 있는 카드를 제일 밑으로 넣어주고

   - Q.pop()                 - 제일 위에 있는 카드를 버려버린다.

   위의 2가지 과정을 계속해서 반복해준다.

   이 때, 주의해야 할 점은 1번과 2번 사이에서 Queue의 Size를 확인해줘야 한다는 것이다.

   1번과정에서 사용된 Q.pop() 연산에 의해서 Queue의 Size가 0이 되어버린다면, 2번과정은 제대로 돌아갈 수 없기 때문이다.

  

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<vector>
 
#define endl "\n"
#define MAX 1000 + 1
using namespace std;
 
int N;
queue<int> Q;
vector<int> V;
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        Q.push(i);
    }
 
    if (Q.size() == 1)
    {
        cout << 1 << endl;
        exit(0);
    }
}
 
void Solution()
{
    int Remainder;
    while (1)
    {
        V.push_back(Q.front());
        Q.pop();
 
        if (Q.size() == 1)
        {
            Remainder = Q.front();
            break;
        }
        Q.push(Q.front());
        Q.pop();
    }
 
    for (int i = 0; i < V.size(); i++)
    {
        cout << V[i] << " ";
    }
    cout << Remainder << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}