덱

“0x07강 - 덱”

덱(deque)

[바킹독 실전 알고리즘] 0x07강 - 덱

워크북 : 백준 1021, 5430

BOJ 1021 (회전하는 큐)


내코도

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <list>
#include <utility>
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;

int N, M, sum;
deque<int>  d;
vector<int> v;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N; cin >> M;

    for (int i = 1; i <= N; i++)
    {
        d.push_back(i);
        v.push_back(i);
    }

    for (int i = 0; i < M; i++)
    {
        int num;
        cin >> num;
        int to_find = v[num - 1];

        int sum1 = 0;
        int sum2 = 0;
        for (int i = 0; i < d.size(); i++)
        {
            if (d[i] == to_find)
                break;
            sum1++;
        }
        for (int i = d.size(); i >= 0; i--)
        {
            if (d[i] == to_find)
                break;
            sum2++;
        }

        if (sum1 < sum2) 
        {
            while (d.front() != to_find)
            {
                int front = d.front();
                d.pop_front();
                d.push_back(front);
                sum++;
            }
        }
        else
        {
            while (d.front() != to_find)
            {
                int back = d.back();
                d.pop_back();
                d.push_front(back);
                sum++;
            }
        }
        d.pop_front();
    }
    cout << sum;
    return 0;
}
  • push_swap을 배열로 만든 환형 큐로 진행하는 게시물을 손수 작성했던 나에게는 매우 매우 익숙했던 문제이지만… 그런 경험이 무색하게도 100줄에 가까운 코드를 싸지르고 말았다. 모법답안을 참고하니 40줄 정도면 끝나더라. 그래도 시간 복잡도는 거의 비슷하다는 것이 위안이다. 아래의 모범답안을 참고하며 반성또반성
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <list>
#include <utility>
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;

int N, M, sum;
deque<int>  d;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> N; cin >> M;

    for (int i = 1; i <= N; i++)
        d.push_back(i);

    while (M--)
    {
        int t;
        cin >> t;   
        int idx = find(d.begin(), d.end(), t) - d.begin();
        while (d.front() != t)
        {
            if (idx < d.size() - idx) {
                d.push_back(d.front());
                d.pop_front();
            }
            else {
                d.push_front(d.back());
                d.pop_back();
            }
            sum++;
        }
        d.pop_front();
    }
    cout << sum;
    return 0;
}
  • deque의 find 매서드를 통해 내가 그렇게 갈구하며 똥꼬쑈를 하며 구했던 인덱스를 한줄에 구해줄수가 있다…

BOJ 5430 (AC)


내코도

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <list>
#include <utility>
#include <sstream>
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;

int tc;

void    reverseDiscard(deque<int>& d, string s)
{
    int r_flag = 0;

    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == 'R')
        {
            if (r_flag == 0)
                r_flag = 1;
            else
                r_flag = 0;
        }
        else if (s[i] == 'D')
        {
            if (d.size() == 0)
            {
                cout << "error\n";
                return;
            }
            if (r_flag == 0)
                d.pop_front();
            else
                d.pop_back();
        }
    }
    
    cout << "[";
    if (r_flag == 0)
    {
        for (int i = 0; i < d.size(); i++)
        {
            cout << d[i];
            if (i != d.size() - 1)
                cout << ',';
        }
    }
    else
    {
        for (int i = d.size() - 1; i >= 0; i--)
        {
            cout << d[i];
            if (i != 0)
                cout << ',';
        }    
    }
    cout << "]\n";
}

void    solve()
{
    string  s; cin >> s;
    int size; cin >> size;

    string  tmp; cin >> tmp;
    deque<int> d;

    string n = "";
    for (int i = 0; i < tmp.length(); i++) 
    {
        if (tmp[i] == '[' || tmp[i] == ']')
            continue ;
        else if (tmp[i] == ',')
        {
            if (n != "")
            {
                int number = stoi(n);
                d.push_back(number);
            }
            n = "";
        }
        else
        {
            n.push_back(tmp[i]);
            if (i == tmp.size() - 2)
            {
                int number = stoi(n);
                d.push_back(number);
            }
        }
    }

    reverseDiscard(d, s);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> tc;

    while (tc--)
        solve();

    return 0;
}
  • 너무 충격적인 문제였다… 어떻게 이런 생각을 할 수 있는 것 인지? 이런걸 생각할 수 있는 사람은 천재가 아닌 지?
  • deque을 reverse하려면 아래와 같이 할 수 있는데
std::reverse(d.begin(), d.end());

여기서 R이랍시고 뒤집으면 시간초과가 난다. deque의 reverse는 O(N)에 진행되는데 이미 for문을 돌면서 reverse하기 때문에 시간복잡도가 N^2가 되고, 테케로 배열이 100,000개가 들어오기 때문에 초과가 난다. 그래서 뒤집은 척을 해야 한다.

  • 이 뒤집은 척을 하려면 Deque을 쓰는게 편하다. 난 처음에 이 문제가 왜 덱 문제집에 있는지 이해하지 못했다. 그러나 덱을 안쓰면 뒤집은 척을 하기가 곤란하다. 예를 들어 벡터는 pop_front를 할수가 없다.