[BaekJoon 2164][⚪4] 카드2

❓ 문제

백준 2164 - “카드2”

🎯 난이도

Silver ⚪4

🧠 풀이

1. 내 풀이 (queue)

- 알고리즘

• Data Structure, queue

- 설명

queue를 사용해서 푸는 풀이이다.

앞의 요소를 제거하고, 다시 뒤에 넣는 방식으로 풀면 되므로, queue를 사용하면 딱 맞다.

queue의 size가 1이 될 때까지 반복문을 돌리는데, 내부적으로는 pop으로 맨 앞의 한 장을 빼고, 다시 맨 앞의 한 장을 뒤로 push한 뒤, 다시 그 카드를 pop하면 된다.

반복문 하나를 돌리므로, 시간 복잡도는 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <queue>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iN{};
    cin >> iN;

    queue<int> qCard{};

    for(int i = 1; i <= iN; ++i)
    {
        qCard.push(i);
    }

	// 1개만 남을 때까지 반복
    while(qCard.size() > 1)
    {
        qCard.pop();	// 맨 앞 pop
        
        qCard.push(qCard.front());	// 맨 앞 뒤로 보냄
        qCard.pop();	// 맨 앞 pop
    }

    cout << qCard.front();

    return 0;
}

---

2. 추가 풀이 (deque)

- 알고리즘

• Data Structure

- 설명

deque을 사용하는 풀이이다.

queue를 사용하는 대신, deque을 사용하는 방식이다.

'queue'와 'stack'은 'deque'을 얇게 래핑하는 '컨테이너 어댑터'이므로, 이 두 컨테이너를 사용하는 문제는 모두 'deque'으로 치환 가능하다.

위와 똑같이 시간 복잡도는 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <deque>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iN{};
    cin >> iN;

    deque<int> dqCard{};

    for(int i = 1; i <= iN; ++i)
    {
        dqCard.push_back(i);
    }

	// 1개만 남을 때까지 반복
    while(dqCard.size() > 1)
    {
        dqCard.pop_front();	// 맨 앞 pop

        dqCard.push_back(dqCard.front());	// 맨 앞 뒤로 보냄
        dqCard.pop_front();	// 맨 앞 pop
    }

    cout << dqCard.front();

    return 0;
}

---

💭 후기

상술한 대로, stack, queue는 모두 deque의 컨테이너 어댑터이므로 치환 가능한 것 뿐만 아니라, 이론상 약간의 성능 차이가 있을 수 있다. 위의 두 컨테이너는 한 번 더 호출을 거쳐야 하는 대신에, deque은 바로 직접적인 호출이기 때문이다. 하지만 굉장히 얇은 래핑을 한 컨테이너 어댑터이므로, 사실상 성능 차이는 거의 없으므로 뭘 써도 상관은 없다고 보는게 맞다.