[알고리즘] 백준알고리즘 10866 Deque 문제

안녕하세요 감자코딩에 감자개발자입니다.

이번에 풀어볼 문제는 백준알고리즘에 10866문제인 Deque를 사용한 문제입니다. 

문제 링크

https://www.acmicpc.net/problem/10866

문제

정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여덟 가지이다.

push_front X: 정수 X를 덱의 앞에 넣는다.

push_back X: 정수 X를 덱의 뒤에 넣는다.

pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

size: 덱에 들어있는 정수의 개수를 출력한다.

empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.

front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘쨰 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

예제 입력 1 

15

push_back 1

push_front 2

front

back

size

empty

pop_front

pop_back

pop_front

size

empty

pop_back

push_front 3

empty

front

예제 출력 1 

2

1

2

0

2

1

-1

0

1

-1

0

3

이렇게 문제를 확인할 수 있습니다.

이제 살펴볼 문제는 Deque가 무엇일까요?

1. 크기가 가변적이다. 
리스트와 같이 데이터를 담을 수 있는 크기가 가변적입니다. 

2. 앞과 뒤에서 삽입과 삭제가 좋다. 
Deque가 다른 자료구조와 가장 다른 점으로 앞과 뒤에서 삽입, 삭제가 좋습니다. 

3. 중간에 데이터 삽입, 삭제가 용이하지 않다. 
데이터를 중간에 삽입하거나 삭제하는 것은 피해야 합니다. 삽입과 삭제를 중간에 한다면 삽입하거나 삭제한 위치 앞뒤 데이터를 모두 이동해야 합니다. 

 
[그림 3] 데이터 g를 중간에 삽입하는 과정 

 
[그림 4] 데이터 c를 삭제하는 과정 

4. 구현이 쉽지 않다. 
Deque은 Stack과 Queue가 결합된 자료구조로 연결 리스트보다 구현하기가 더 어렵습니다. 

5. 랜덤 접근이 가능하다. 

연결 리스트처럼 리스트를 탐색하지 않고 원하는 요소에 바로 접근할 수 있습니다.

위 문제에서 정의한것과 같이 

Deque는 스택과 큐를 혼합시킨것이라고 생각할 수 있습니다. 저장공간에서 앞에서도 Push & Pop 을 할 수 있고, 뒤에서도 Push & Pop을 실행 할 수 있습니다.

그래서 저는 이번문제에서는 C++ 라이브러리인 Deque를 사용해서 문제를 해결해보려합니다.

맨처음에는 배열이나, 벡터를 사용해서 풀어보려고 하였으나, 생각보다 구현이 까다로울것이라고 생각이 들어서 C++ STL Deque를 사용하였습니다.

Deque를 사용하기 앞서, 자료 구조형태인 Vector, Stack, Queue를 한번 정리하고 가면 좋을것 같습니다. 비교해서 차이점을 알면 더욱더 좋겠습니다.

deque VS vector

deque는 전체적으로 멤버 함수의 기능이나 사용 방법이 vector와 거의 같습니다. vector는 삽입과 삭제를 뒤(back)에서만 해야 성능이 좋지만, deque는 삽입과 삭제를 앞과 뒤에서 해도 좋으며 앞뒤 삽입, 삭제 성능도 vector보다 좋습니다. 하지만, deque는 앞뒤에서 삽입, 삭제하는 것을 제외한 다른 위치에서의 삽입과 삭제는 vector보다 성능이 좋지 않습니다. 

	deque	vector
크기 변경 가능	O	O
앞에 삽입, 삭제 용이	O	X
뒤에 삽입, 삭제 용이	O	O
중간 삽입, 삭제 용이	X	X
순차 접근 가능	O	O
랜덤 접근 가능	O	X

[표 1] deque와 vector의 차이 

deque와 vector를 비교할 때 고려해야 되는 점은 
deque는 앞과 뒤에서 삽입과 삭제 성능이 vector보다 더 좋다. 
deque는 앞과 뒤 삽입, 삭제를 제외한 기능은 vector보다 성능이 좋지 못하다. 

문제 해결 방법

1) 가장먼저 문제에서 입력을 원하는 방식은 총 명령어수의 수를 cin을 사용하여 입력을 받습니다.

2) 그 이후에 각 명령어 별로 Deque 함수를 사용하여 조건에 따라 처리하였습니다.(8개의Command)

3) 저는 원래 출력과 입력형식을 printf와 scanf를 사용하였는데, 자꾸 출력형식이 잘못되었다는 에러를 뱉어서 입출력을 cout/cin형식으로 모두 바꾸어 처리해주었습니다.

코드 리뷰 

//

//  10866(Deque).cpp

//  Algorigm_Study

//

//  Created by kgh on 18/12/2018.

//  Copyright © 2018 kgh. All rights reserved.

//

#include <stdio.h>

#include <iostream>

#include <vector>

#include <deque>

#include <string>

using namespace std;

int main(void){

    // STL deque 선언

    deque<int> q;

    // cmd_cnt 변수 값 선언 및 입력

    int cmd_cnt = 0;

    cin >> cmd_cnt;

    // cmd_cnt 값만큼 while문 실행 시간복잡도: 빅오O(N)

    while(cmd_cnt--){

        string str;

        cin >> str;

        // push_front 명령일 경우

        if(str == "push_front"){

            int num =0;

            cin >> num;

            q.push_front(num);

        // push_back 명령일 경우

        }else if(str == "push_back"){

            int num =0;

            cin>>num;

            q.push_back(num);

        // pop_front 명령일 경우

        }else if(str == "pop_front"){

            if(!q.empty()){

                cout << q.front() << endl;

                q.pop_front();

            }else{

                cout << "-1" << endl;

            }

        // pop_back 명령일 경우

        }else if(str == "pop_back"){

            if(!q.empty()){

                cout << q.back() <<endl;

                q.pop_back();

            }else{

                cout << "-1" <<endl;

            }

        // size 명령일 경우

        }else if(str == "size"){

            cout << q.size() << endl;

        }else if(str == "empty"){

            if(!q.empty()){

                cout << "0" <<endl;

            }else{

                cout << "1" <<endl;

            }

        // empty 명령일 경우

        }else if(str == "empty"){

            if(!q.empty()){

                cout << "0" <<endl;

            }else{

                cout << "1" << endl;

            }

        }

        // front 명령일 경우

        else if(str == "front"){

            if(!q.empty()){

                cout << q.front() << endl;

            }else{

                cout << "-1" << endl;

            }

        // back 명령일 경우

        }else if(str == "back"){

            if(!q.empty()){

                cout << q.back() << endl;

            }else{

                cout << "-1" << endl;

            }

        }

    }

    return 0;

}

간단한 deque를 사용한 문제였습니다. 난이도가 그렇게 높지는 않았지만, 출력형식에서 삽질을 좀 했습니다.

감자코딩에 감자개발자 였습니다 :)

Reference: 한빛미디어(Deque)