Deque, 덱 , 자료구조 [CPP]

 

이번엔 자료구조에서 덱을 보겠다.

 

 

덱은 스택과 큐를 합친 구조라고 볼 수 있다.

삽입,삭제가 front, back에서 다 일어날 수 있다.

C++에서 Stack,Queue는 덱에서 인터페이스를 제한해서 구현한 것이다.

-> 즉, 덱에서 기능을 제한해서 구현했다는 뜻이다.

 

** 원칙적으로는 front와 back에서만 접근이 가능하지만

STL deque에서는 인덱스로 원소 접근이 가능하다.

 

덱의 특성 때문에 배열과 뭐가 다른가..? 생각이 들 때가 있다.

앞쪽과 뒤쪽의 추가와 제거가 모두 필요하면 deque를 사용

배열의 느낌으로 사용하려면, vector를 사용

 

거꾸로 말하면 Deque으로 Queue를 사용해야하는 문제나 Stack을 사용해야하는 문제를

풀 수 있다는 말도 된다.

 

---

 

생성자는 이렇다.

deque<type> dq	빈 컨테이너 dq
deque<type> dq(n)	0으로 초기화된 n개의 원소를 갖는 덱 dq
dequer<type> dq(n, x)	x로 초기화된 n개의 원소를 갖는 덱 dq
deque<type> dq(iterator begin, iterator end)	iterator begin 부터 end 구간으로 초기화된 원소를 갖는 덱 dq

 

관련 함수는 이렇다.

dq.assign(n, x) dq.assign(iterator begin, iterator end)	기존 덱 요소를 지우고 덱를 복사
dq.at(index)	덱의 지정된 위치에 있는 요소를 참조 반환
dq.back()	덱의 마지막 요소에 대한 참조 반환
iter = dq.begin()	덱의 첫 번째 요소에 대한 임의 액세스 반복자를 반환
dq.capacity()	덱에 할당된 공간(capacity) 크기를 반환
dq.clear()	덱의 모든 요소를 지움
dq.emplace(iterator i, x)	내부에서 생성된 요소를 덱의 지정된 위치에 삽입
dq.emplace_back(x)	생성된 요소를 덱의 끝에 추가
dq.emplace_front(x)	생성된 요소를 덱의 시작부분에 추가
dq.empty()	덱 컨테이너가 비어 있는지 조사
iter = dq.begin()	덱 끝을 가리키는 임의 액세스 반복기를 반환
dq.erase(iterator i) dq.erase(iterator begin, iterator end)	덱의 지정된 위치에서 요소 또는 요소 범위를 제거
dq.front()	덱의 첫 번째 요소에 대한 참조를 반환
dq.insert(iterator i, x) dq.insert(iterator i, n, x) dq.insert(iterator begin, iterator end, iterator i)	요소 또는 요소의 수 만큼을 덱의 지정된 위치에 삽입
dq.max_size()	덱의 최대 허용 길이를 반환
dq.pop_back()	덱의 끝에 있는 요소를 삭제
dq.pop_front()	덱의 시작 부분에 요소를 삭제
dq.push_back(x)	덱 끝에 요소를 추가
dq.push_front(x)	덱 시작 부분에 요소를 추가
dq.resize(n) dq.resize(n, x)	덱의 새 크기를 지정
dq.size()	덱에 있는 요소 수를 반환
dq1.swap(dq2)	두 덱의 요소를 교환

 

 

4개의 예제를 통해서 쓰임을 알아보자

 

순서대로 알아보자(세훈이는 .. 나중에 풀래)

www.acmicpc.net/problem/17952

www.acmicpc.net/problem/17225

programmers.co.kr/learn/courses/30/lessons/42586

programmers.co.kr/learn/courses/30/lessons/42584

 

---

첫번째 문제를 보니

스케줄링 문제다

하지만 삽입과 삭제가 한곳에서만 일어난다.

Stack의 냄새가 난다. 

현재 스택의 top에서 실행하고 실행시간이 다 차면 나오는 식으로 생각되었다.

 

#include <iostream>
#include <stack>

int sum = 0;
int time; //주어진 시간
    
//2가지 값을 넣기 위한 stack 만들기
std::stack<std::pair<int, int>> stk;

int main(){

    std::cin>> time;
    for(int i=0; i<time; i++){
        int check; // 1인지 0인지
        std::cin>> check;
        if(check == 1){
            int score; // 점수
            int amountTime; //걸리는 시간
            std::cin >> score >> amountTime;
            stk.push({score,amountTime}); // 집어넣음
        }
        
        if(!stk.empty()){ // 스택이 비어있지 않아야함.
            // 맨 위에 값을 꺼냄
            int a = stk.top().first;
            int b = stk.top().second;
            
            b -= 1; // 1분 소요함
            if(b == 0){ // 과제 다했으면 스택에서 꺼냄
                sum += a;
                stk.pop();
            }
            else{ // 못했으면 1분 소요된 값을 다시 대체해서 넣음
            stk.pop();
            stk.push({a,b});
            }    
        }
    }
    std::cout << sum;
      
}

 

**std::pair로 들어간 스택이면 반환할 때도 pair로 나올 것이다.

 

pair의 요소에 접근할 때는 member로 접근할 수 있다.

 

 

 

---

 

세 번째 문제

큐를 이용하면 될 것 같다.

첫 번째 기능이 출시하기 전까지 두 번째 기능을 출시할 수 없다.

-> 선입선출이다.

 

#include <string>
#include <vector>
#include <queue>
using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    vector<int> answer;
    queue<pair<int,int>> q;
    int time = 1; // 현재 날짜
    
    //큐에 넣음
    for(int i = 0; i < progresses.size(); i++){
        q.push({progresses[i], i});
    }
    
    
    int cnt = 0; // 기능의 개수
    
    //큐에서 빼는 조건
    while(!q.empty()){
        
        //현재 맨 앞의 원소의 값이 시간에 따라 달라짐.
        int a = q.front().first, b = speeds[q.front().second] * time;
        
        //100보다 작으면 넘어감
        if(a + b < 100){
            time++;
            //cnt 가 있다는 것은 거기까지는 출시했다는 것
            if(cnt != 0){
                answer.push_back(cnt);
                cnt = 0; // 초기화
            }
            continue;
        }
        
        //100 넘으면 기능 개수 + 1 하고 해당 원소 pop
        if(a +b >= 100){
            cnt++;
            q.pop();
        }
    }
    //마지막 원소는 if(cnt != 0)을 돌지 않기 때문에 따로 추가
    answer.push_back(cnt);
    

    return answer;
}

 

 

---

주식가격이다.

나중에 삽입되는 것이 해당 가격보다 낮으면 그 때 기록해야 한다.

?? 큐인가?? 스택인가???

스택이다.

해당 원소가 삽입될 때, 맨 위에 있는 원소보다 낮으면 그 때 빼버리면 된다.

 

근데 이건 스택을 이용하면 더 생각이 어려운 풀이였다.. 우선 나는 그랬다.

 

vector<int> solution(vector<int> prices) {
    vector<int> answer(prices.size(), 0);
    stack<pair<int, int>> st;

    for(int i = 0; i < prices.size(); i++) {
        int price = prices[i];
        while(!st.empty() && st.top().second > price) {
            pair<int, int> p = st.top(); st.pop();
            answer[p.first] = i - p.first;
        }
        st.push({i, price});
    }
    
    while(!st.empty()) {
        pair<int, int> p = st.top(); st.pop();
        answer[p.first] = prices.size() - p.first - 1;
    }
    
    return answer;
}

 

이제 대충 감을 익혔으니.. 문제를 풀어보면서 큐,스택을 마스터해보자

 

 

---

참고링크

github.com/VSFe/Algorithm_Study

docs.microsoft.com/ko-kr/cpp/standard-library/deque-class?view=msvc-160