vector를 이용할 시 시간초과 문제발생
298
작성한 질문수 7
안녕하세요.
해당 문제를 vector로 풀려고 하는데 계속 시간 초과가 발생해서 질문을 드립니다.
혹시 어느 부분에서 시간초과가 발생하는지 알 수 있을까요?
vector자체가 시간이 조금 많이 걸리는 걸까요?
#include<bits/stdc++.h>
using namespace std;
int T, n, num;
string p, l;
vector<int> v;
bool rev, error;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> T;
while(T--){
rev = false;
error = false;
cin >> p >> n >> l;
for(char c : l){
if(c >= '0' && c <= '9'){
num = num * 10 + (c - '0');
}
if((c == ',' || c == ']') && num > 0){
v.push_back(num);
num = 0;
}
}
for(char c : p){
if(c == 'R')
rev = !rev;
else{
if(v.size()){
if(rev)
v.pop_back();
else
v.erase(v.begin());
}
else{
error = 1;
}
}
}
if(error){
cout << "error\n";
}
else{
if(rev)
reverse(v.begin(), v.end());
cout << "[";
for(int i = 0; i < v.size(); i++){
cout << v[i];
if(i < v.size() - 1)
cout << ",";
}
cout << "]\n";
}
v.clear();
}
}
답변 1
0
안녕하세요. ㅎㅎ
vector를 사용해서라기보다는
vetor의 erase때문에 그렇습니다. erase의 시간복잡도는 최악의 경우 O(N)의 시간복잡도를 가집니다. begin부터 해서 O(1)인 것 같지만 최악의 시간복잡도가 그러합니다.
그렇기 때문에 deque를 써야 하는 것이죠. deque의 pop_front()는 무조건 O(1)의 시간복잡도거든요.
감사합니다.
1-E질문입니다!
0
533
2
3-L 틀린 부분 피드백 부탁드립니다.
0
835
2
1-A문제 순열재귀함수 질문입니다.
0
396
1
1-A 일곱난쟁이문제입니다
0
470
1
문제 풀 때 방향성에 대해
0
810
1
맥에서 vs code로 실행 관련 질문입니다
0
530
1
17071번 메모리 초과
0
390
1
1-C질문입니다!
0
428
2
2-B BFS 시간초과질문
0
638
2
1-O 13번 라인
0
447
1
6-J 놀이공원 문제 질문
0
389
1
구현관련 질문
0
491
1
강의 교안
0
322
1
실력을 더 올리고나서 강의를 보는 것이 맞을까요?
0
550
1
안녕하세요! 재귀함수에 관해서 질문드립니다
0
540
1
1-K
0
481
2
3-G번 질문있습니다.
1
480
3
3-C 실행 시간 질문드립니다.
0
503
1
4-A 문제 풀이 질문있습니다.
0
601
2
비트마스킹 연산자 "1의 보수" 영문 표기법
0
441
1
격자탐색 문제에서 BFS 시간복잡도 질문드립니다.
0
349
1
3-O go 함수 질문 드립니다.
1
453
2
4-A 출력 질문
0
308
1
1주차 1-O 질문드립니다
0
266
1





