[BOJ] 백준 28279번: 덱 2 (C++)

 

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

---

1. 생각

이번에는 deque (덱) 이라는 자료구조를 가지고 왔다.

queue와 굉장히 유사하지만, pop을 front에서만 할 수 있던 queue와 다르게

pop_front(), pop_back(), push_front(), push_back() 과 같이 앞 뒤 모두 데이터의 입출력이 되는 구조이다.

 

이 문제는 queue와 stack을 처음 시작할 때처럼 기본 기능을 명령어를 통해 받는 문제이다.

deque에 대해 알아보는 내용을 한번 쭉 살펴보도록 하겠다.

 

2. 난관 & 해결 방법

#include <iostream>
#include <deque>

 

 역시 deque도 include 해주고 시작한다.

 

std::deque <int> dq;
int n, com, input;
std::cin.tie(NULL);
std::ios::sync_with_stdio(false);

 

deque의 초기화 방식도 다른 자료구조와 동일하다.

std::deque <자료형> 이름; 으로 선언하고 시작한다.

 

이번 과제도 일반 cin으로만 받으면 시간초과가 나와서 tie와 sync_with_stdio를 이용해 속도를 빠르게 만들었다.

 

    for (int i = 0; i < n; i ++){
        std::cin >> com;
        switch (com) {
        case 1:
            std::cin >> input;
            dq.push_front(input);
            break ;
        case 2:
            .
            .
            . (중략)
            .
            .
        case 8:
            if (dq.empty()){
                std::cout << "-1\n";
                break ;
            }
            std::cout << dq.back() << "\n";
            break ;
        }
    }

 

if - else if 를 잔뜩 쓰려다가, switch - case 문을 거의 써보지 않아서 한번 써봤다.

if문이 3개 이상이 될 때부터는 switch-case문이 더욱 효율이 좋다고 한다.

 

8가지의 명령어가 있기 때문에 하나하나 다 deque의 함수들을 이용하여 만들어줬고,

기존 queue와 동일하지만 _front, _back 이 pop과 push에 추가되어 활용성이 더 크게 만들어져있다.

3. 코드 및 결론

[ 전체 코드 ]

#include <iostream>
#include <deque>

int main(void){
    std::deque <int> dq;
    int n, com, input;
    std::cin.tie(NULL);
    std::ios::sync_with_stdio(false);
    std::cin >> n;
    for (int i = 0; i < n; i ++){
        std::cin >> com;
        switch (com) {
        case 1:
            std::cin >> input;
            dq.push_front(input);
            break ;
        case 2:
            std::cin >> input;
            dq.push_back(input);
            break ;
        case 3:
            if (dq.empty()){
                std::cout << "-1\n";
                break ;
            }
            std::cout << dq.front() << "\n";
            dq.pop_front();
            break ;
        case 4:
            if (dq.empty()){
                std::cout << "-1\n";
                break ;
            }
            std::cout << dq.back() << "\n";
            dq.pop_back();
            break ;
        case 5:
            std::cout << dq.size() << "\n";
            break ;
        case 6:
            if (dq.empty())
                std::cout << "1\n";
            else
                std::cout << "0\n";
            break ;
        case 7:
            if (dq.empty()){
                std::cout << "-1\n";
                break ;
            }
            std::cout << dq.front() << "\n";
            break ;
        case 8:
            if (dq.empty()){
                std::cout << "-1\n";
                break ;
            }
            std::cout << dq.back() << "\n";
            break ;
        }
    }  
}

 

[ 결론 ]

 

deque 라는 자료구조에 대해서 알아보았다.

stack 과 queue의 기능 (FIFO, LIFO)을 모두 사용 가능한 구조이며,

양 끝에서 삽입 및 삭제가 가능하다는 장점을 가지고 있지만,

그만큼 메모리 사용량이 크다는 단점도 있다고 한다.

 

상황에 맞게 자료구조를 쓸 수 있는 능력을 길러보자.