글 읽기 - vector와 deque 차이

wogks99 1년 전 0

초기에 vector를 사용해서 문제를 풀었는데 시간초과가 나서 deque를 사용해서 다시 푸니까 해결했습니다.

하지만 왜 vector를 사용하면 터지고 deque를 사용하면 안터지는지 모르겠습니다.

erase와 pop의 차이때문일까요? 너무 궁금합니다!!

/*
vector사용
백준 골드5 AC
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <deque>
using namespace std;
deque<int>dq;
int T;
bool flag,err;
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> T;
    for (int i = 0; i < T; i++)
    {
        flag = true,err=1; // true가 정방향, false가 역방향
        string str, arr, now;
        int Size,len=0;
        vector<string> answer;
        cin >> str >> Size >> arr;
        for (int j = 0; j < arr.size(); j++)
        {
            if (isdigit(arr[j])) {
                now+=arr[j];
            }
            else {
                if (now.empty() == 0) {
                    answer.push_back(now);
                    len++;
                    now = "";
                }
            }
        }
        for (int k = 0; k < str.size(); k++) {
            if (str[k] == 'R') {
                if (flag == true) {
                    flag = false;
                }
                else {
                    flag = true;
                }
            }
            else {
                if (answer.empty() == 1) {
                    cout << "error" << '\n';
                    err = false;
                    break;
                }
                else
                {
                    if (flag == 1) {
                        answer.erase(answer.begin());
                        len--;
                    }
                    else
                    {
                        answer.erase(answer.end()-1);
                        len--;
                    }
                }
            }
        }
        if (err == 1) {
            cout << "[";
            if (flag == 1) {
                for (int x = 0; x < len; x++) {
                    if (x != len - 1) {
                        cout << answer[x] << ",";
                    }
                    else
                        cout << answer[x];
                }
                cout << "]"<<"\n";
            }
            else {
                for (int x = len - 1; x >= 0; x--) {
                    if (x != 0) {
                        cout << answer[x] << ",";
                    }
                    else
                        cout << answer[x];
                }
                cout << "]" << "\n";
            }
        }
    }
}
/*
deque사용
백준 골드5 AC
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <deque>
using namespace std;
deque<int> dq;
int T;
bool flag, err;
void ac(string str, vector<string> &n);
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> T;
    for (int i = 0; i < T; i++)
    {
        flag = true, err = 0; // true가 정방향, false가 역방향
        string str, arr, now;
        int Size;
        vector<string> answer;
        cin >> str >> Size >> arr;
        // cout<<str<<endl;
        for (int j = 0; j < arr.size(); j++)
        {
            if (isdigit(arr[j]) != 0) //숫자라는소리임
            {
                now += arr[j];
            }
            else
            {
                if (!now.empty())
                {
                    dq.push_back(stoi(now));
                    now = "";
                }
            }
        }
        for (int k = 0; k < str.size(); k++)
        {
            if (str[k] == 'R')
            {
                if (flag == false)
                {
                    flag = true;
                }
                else
                    flag = false;
            }
            else
            { // str[k]==D
                if (dq.size() == 0)
                {
                    cout << "error" << endl;
                    err = 1;
                    break;
                }
                else
                {
                    if (flag == 1)
                    {
                        dq.pop_front();
                    }
                    else
                        dq.pop_back();
                }
            }
        }
        if (err != 1)
        {
            if (flag == 1)
            { //정방향
                cout << '[';
                while (dq.size() != 0)
                {
                    if (dq.size() != 1)
                        cout << dq.front() << ',';
                    else
                    {
                        cout << dq.front();
                    }
                    dq.pop_front();
                }
                cout << ']';
            }
            else
            {   //역방향
                cout << '[';
                while (dq.size() != 0)
                {
                    if (dq.size() != 1)
                    {
                        cout << dq.back() << ',';
                    }
                    else
                    {
                        cout << dq.back();
                    }
                    dq.pop_back();
                }
                cout << ']';
            }
            cout << endl;
        }
    }
}

Complexity

Linear: the number of calls to the destructor of T is the same as the number of elements erased, the assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

vector와 deque 차이

wogks99 1년 전 0

shjohw12 1년 전 0

Complexity

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말