[BOJ] 백준 2164번: 카드 2 (C++)

 

- 문제 출처 : https://www.acmicpc.net/problem/2164

---

1. 생각

저번 문제에 이어, 큐를 활용하는 문제를 가져왔다.

로직 자체는 엄청 간단하게 보인다.

 

가장 위의 카드를 버리기 -> 다음 위의 카드를 밑에 옮기기

이 형태를 재해석하게 되면,

front 카드 pop() -> push (front 카드번호) -> front 카드 pop()

 

으로 큐에 맞게 해석했다.

옮기는 행위를 직접적으로 할 수 있는 수단이 없어서,

pop하기 전에 미리 해당 번호의 카드를 push 해두는 방식을 취하기로 했다.

 

2. 난관 & 해결 방법

int n;
std::queue <int> q;

std::cin >> n;

 

카드의 총 개수를 n으로 받았다.

그리고 queue를 만들어주었다.

 

for (int i = 0; i < n; i ++)
{
    q.push(i + 1);
}
while (q.size() > 1)
{
    q.pop();
    if (q.size() == 1)
        break ;
    q.push(q.front());
    q.pop();
}
std::cout << q.front() << "\n";

 

그리고 메인 로직인데, 우선은 이 카드들을 모두 처음부터 끝까지 queue에 담아줘야 하므로,

for문을 통해 인덱스 + 1 (인덱스가 0부터지만, 카드는 1부터 시작하므로) 에 해당하는 카드를 push 해줬다.

 

그리고 새로 while문을 하나 만들어서, queue의 size가 1보다 클 동안 반복하도록 한다.

처음에는 pop(), 그리고 그 다음 과정 전에 size가 1이 되었는지 미리 체크하고 다시 돌린다.

그 후 push(front) 과정으로 카드를 먼저 복사하여 주고, pop해준다.

 

마지막 남은 카드를 cout으로 출력해주면 끝이다.

 

3. 코드 및 결론

[ 전체 코드 ]

#include <iostream>
#include <queue>

int main(void){
    int n;
    std::queue <int> q;

    std::cin >> n;
    for (int i = 0; i < n; i ++)
    {
        q.push(i + 1);
    }
    while (q.size() > 1)
    {
        q.pop();
        if (q.size() == 1)
            break ;
        q.push(q.front());
        q.pop();
    }
    std::cout << q.front() << "\n";
}

 

[ 결론 ]

 

큐를 활용하는 문제를 가져왔는데, 상당히 로직이 단순해서 쉽게 짰다.

자료구조 문제들을 풀어보면서 느낀 점은 어떤 문제들이 잔뜩 쏟아졌을 때,

이 문제는 큐, 어떤 문제는 스택.. 이런 식으로 쉽게 분류할 수 있는 능력이 갖춰져야

문제 해결력이 정말 탄탄해지지 않을까 싶다.

 

다른 자료구조들도 하나씩 풀어보며 기반을 잘 쌓아보도록 하겠다.