[STL 컨테이너] deque 한번에 정리하기

▶ [STL] deque 컨테이너

---

vector 컨테이너는 컨테이너의 맨 앞에 원소를 추가하는 멤버함수가 없다.

배열의 맨 앞이나 중간에 원소를 추가하려면 나머지 원소들을 모두 뒤로 한 칸씩 이동시켜야한다.

vector 컨테이너는 배열 기반으로 구현되어있으므로 원소를 앞이나 중간에 삽입하는 기능이 매우 비효율적으로 동작하게 된다.

또한 배열의 사이즈를 초과하는 경우 사이즈를 늘려서 재할당하고 기존의 값을 복사해주는데, 이 작업도 오버헤드가 크다.

deque는 컨테이너의 앞과 뒤로 삽입과 삭제가 자유롭도록 구현되어있다.

deque도 배열 기반으로 구현되어있지만,

원소를 앞으로 밀어내거나 뒤로 밀어내는 게 가능해졌기 때문에 vector의 삽입 연산보다는 좀 더 빠르게 동작한다.

컨테이너에 대해 알고싶다면 아래의 링크를 클릭하세요.

link : 컨테이너란?

deque 컨테이너의 자주 사용되는 생성자와 멤버 함수를 살펴보자.

더 다양한 함수들이 있지만 개인적으로 알고리즘 문제를 해결하는데는 이정도만 알아도 충분하다고 생각한다.

# deque 생성자

선언	설명
deque dq	빈 컨테이너를 생성
deque dq(n)	컨테이너에 n개의 원소를 저장하여 생성(default 값 저장)
deque dq(n,x)	컨테이너에 n개의 원소를 저장하는데, x의 값을 넣어서 생성
deque dq(dq2)	dq2와 똑같은 원소를 가지는 컨테이너를 생성

# deque 멤버 함수

호출	설명
dq.push_back(x)	마지막 원소 뒤에 x를 삽입한다.
dq.push_front(x)	첫번째 원소 앞에 x를 삽입한다.
dq.pop_back()	마지막 원소를 삭제한다.
dq.pop_front()	첫번째 원소를 삭제한다.
dq.clear()	모든 원소를 삭제한다.
dq.empty()	dq에 원소가 하나도 없으면 true, 아니면 false를 리턴한다.
iter = dq.begin()	dq의 첫 번째 원소를 가리키는 반복자를 리턴한다.
iter = dq.end()	dq의 마지막 원소 다음을 가리키는 반복자를 리턴한다.
dq.size()	원소의 개수를 리턴한다.
n_iter = dq.erase(iter)	iter가 가리키는 원소를 삭제한다. 그리고 다음 원소를 가리키는 반복자를 리턴한다.
dq.back()	마지막 원소를 리턴한다.
dq.front()	첫번째 원소를 리턴한다.

# 원소 참조 방법

dq[idx]	idx번째 원소를 참조한다. (범위에 대한 예외처리 X)
dq.at(idx)	idx번째 원소를 참조한다. (범위에 대한 예외처리 O)

반복자에 대해 알고싶다면 아래의 링크를 클릭하세요.

link : 반복자란?

아래의 문제를 해결할 때, 위에 있는 deque 생성자와 멤버 함수를 어떻게 활용하는지 보고 익혀보도록 하자.

▶ 문제

---

n을 입력받아서 n개의 데이터를 저장할 수 있는 vector를 선언하고 

0으로 초기화 시키되 인덱스 0과 5의 배수가 되는 인덱스에 1을 저장해보자.

( 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 ... 0 0 0 0 1 이런 식으로 저장하면 된다. )

▷요구 조건 1 : n과 관계 없이 항상 마지막은 1로 끝나도록 구현하라.

n이 7인 경우를 예를 들면,

결과 값이 [ 1 0 0 0 0 1 0  ] 이 아니라

뒤에 값을 더 추가해서 [ 1 0 0 0 0 1 0 0 0 0 1 ] 이 되도록 구현해야한다.

▷요구 조건 2 : 왼쪽으로 5번 회전시킨 결과와 오른쪽으로 2번 회전시킨 결과를 출력하라.

요구 조건 1을 만족시킨 결과가 [ 1 0 0 0 0 1 0 0 0 0 1 ] 이라면,

출력은 [ 1 0 0 0 0 1 1 0 0 0 0], [ 0 1 1 0 0 0 0 1 0 0 0 ] 이 되어야 한다.

▶ 설계

---

deque를 선언하면서 n개의 공간을 0으로 채우고,

5의 배수가 되는 인덱스에 1을 채우면서 인덱스를 증가시키다가

인덱스가 n이상이 되면 할당되어있는 공간의 마지막 인덱스에서 가장 가까운 1의 인덱스까지 0이 몇 개인지 세어서 문제에서 요구하는 조건을 만족시키도록 값을 채워 넣어 요구 조건 1을 만족시키자.

deque를 왼쪽으로 회전시키려면 첫번째 원소를 빼서 마지막 원소 뒤로 옮기면 되고,

deque를 오른쪽으로 회전시키려면 마지막 원소를 빼서 첫번째 원소 앞으로 옮기면 된다.

▶ 구현

---

우선 어떤 형태로 함수를 정의할지 선언하고 main문을 작성해보자.

[main.cpp]

deque<int> meetRequire1(const deque<int>& dq);
deque<int> leftRotation(const deque<int>& dq, int num);
deque<int> rightRotation(const deque<int>& dq, int num);
void printDq(const deque<int>& dq);
 
int main(){
    int n;
    cin >> n;
    deque<int> dq(n, 0);
    deque<int> resDq1 = meetRequire1(dq);
    deque<int> resDq2 = leftRotation(resDq1, 5);
    printDq(resDq2);
    deque<int> resDq3 = rightRotation(resDq1, 2);
    printDq(resDq3);
 
    return 0;
}

line	설명
1	meetRequire1()은 deque를 인자로 받아 요구 조건 1을 만족시키는 벡터 컨테이너를 반환하도록 선언했다.
2	leftRotation() deque를 인자로 받아 왼쪽으로 num만큼 회전시킨 결과를 리턴하도록 선언했다.
3	rightRotation() deque를 인자로 받아 오른쪽으로 num만큼 회전시킨 결과를 리턴하도록 선언했다.
4	deque를 인자로 받아 출력시키는 기능을 하도록 선언했다.
7~9	n을 입력받아 n 사이즈의 deque 컨테이너에 0을 넣어서 생성했다.
10~14	요구 조건 1과 2를 만족시키는 deque를 반환받아 출력하도록 구현했다.

이제 함수들을 정의해보자.

[요구 조건 1]

deque<int> meetRequire1(const deque<int>& dq){
    deque<int> retDq(dq);
    int end = retDq.size();
    for(int i=0; i<end; i+=5){
        retDq[i] = 1;
    }
    if(retDq.back() != 1){
        int cnt = 1;
        while(retDq[end-1-cnt] != 1){
            cnt++;
        }
        for(int i=0; i<4-cnt; i++)
            retDq.push_back(0);
        retDq.push_back(1);
    }
    return retDq;
}

line	설명
2	retDq는 dq의 원소를 복사하여 생성된다.
3~6	인덱스 0과 5의 배수에 1을 저장해주고 있다.
7	retDq의 마지막 인덱스가 1이 아닌지 확인한다.
8~11	ret의 마지막 인덱스에서부터 앞으로 보면서 마지막으로 나온 1 뒤에 0이 몇 개 있는지 카운팅한다.
12~13	4-cnt개 만큼 뒤에 0을 더 삽입한다.
14	마지막에 원소 1을 삽입한다.

[왼쪽으로 회전]

deque<int> leftRotation(const deque<int>& dq, int num){
    deque<int> resDq(dq);
 
    for(int i=0; i<num ;i++){
        int e = resDq.front();
        resDq.pop_front();
        resDq.push_back(e);
    }
 
    return resDq;
}

line	설명
2	retDq는 dq의 원소를 복사하여 생성된다.
4~8	retDq를 왼쪽으로 num번 회전시킨다.
5~6	retDq의 첫번째 원소를 e에 저장한 뒤 첫번째 원소를 삭제한다.
7	e를 마지막 원소 뒤에 삽입한다.

[오른쪽으로 회전]

deque<int> rightRotation(const deque<int>& dq, int num){
    deque<int> resDq(dq);
 
    for(int i=0; i<num ;i++){
        int e = resDq.back();
        resDq.pop_back();
        resDq.push_front(e);
    }
 
    return resDq;
}

line	설명
2	retDq는 dq의 원소를 복사하여 생성된다.
4~8	retDq를 오른쪽으로 num번 회전시킨다.
5~6	retDq의 마지막 원소를 e에 저장한 뒤 마지막 원소를 삭제한다.
7	e를 첫번째 원소 앞에 삽입한다.

[출력]

void printDq(const deque<int>& dq){
    cout<<"[ ";
    for(int i=0; i<dq.size(); i++)
        cout<<dq[i]<<" ";
    cout<<"]"<<endl;
}

단순히 deque를 순회하면서 출력하도록 구현했다.

▶ 결과

---

▶Solution

---

[소스코드 보기]