백준 5430 c++

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

5430번: AC

 

덱을 한번도 안써봐서 vector로 구현하려다 크게 혼난 문제

 

vector의 경우 첫번째 인덱스에 값을 집어넣으려면 첫번째 인덱스에 값이 들어가고 나머지 인덱스들을 하나씩 복사해서 뒤로 밀려나는 구조입니다.

 

이런 구조는 벡터의 size가 커질수록 성능이 저하됩니다.

 

그래서 단점을 극복하기 위해 deque 컨테이너가 만들어졌습니다.

deque은 메모리가 부족할때 마다 일정한 크기의 새로운 메모리 블록을 할당함으로써 이전 원소를 복사하지 않습니다.

 

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
using namespace std;

int string_to_num(string str)
{
	reverse(str.begin(),str.end());
	int result = 0;
	for(int i=0; i<str.length(); i++) {
		result = result + ( (str[i]-'0') * pow(10,i));
	}
	return result;
} 

int main(void)
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	int t;
	cin >> t;
	
	for(int i=0; i<t; i++) {
		deque<int> v;
		string str,num,num_tmp;
		cin >> str;
		int tmp;
		cin >> tmp;
		cin >> num;
		bool check = true;	//true 일때는 맨앞을 지우고 false 일때는 뒤를 지움 
		bool c = true;
		if(tmp != 0) {
			for(int j=0; j<num.length(); j++) {
				if(num[j] == '[')	continue;
				if(num[j] == ']') {
				    if(num_tmp == "") {
				        continue;
				    }
					v.push_back(string_to_num(num_tmp));
				}
				if(num[j] == ',') {
					v.push_back(string_to_num(num_tmp));
					num_tmp = "";
				}
				else {
					num_tmp = num_tmp + num[j];
				}
			}
		}
		
		for(int j=0; j<str.length(); j++) {
			if(str[j] == 'D') {
				if(v.size() == 0) {
					c = false;
					break;
				}
				if(check) {
					v.pop_front();
				}
				else {
					v.pop_back();
				}
			}
			else {
				check = !check;
			}
		}
		
		
		if(!c) {
			cout << "error" << endl;
		}
		else {
			if(check) {
				cout << "[";
				for(int j=0; j<v.size(); j++) {
					cout << v[j];
					if(j != v.size()-1) {
						cout << ",";
					}
				}
				cout << "]" << endl;
			}
			else {
				cout << "[";
				for(int j=v.size()-1; j>=0; j--) {
					cout << v[j];
					if(j != 0) {
						cout << ",";
					}
				}
				cout << "]" << endl;
			}
		}
		
	}	
	
	return 0;
}

 

** 문자열에서 앞 뒤를 지우는 경우가 나오면 deque을 사용해 성능을 올리자!