inflearn logo
강의

강의

N
챌린지

챌린지

멘토링

멘토링

N
클립

클립

로드맵

로드맵

지식공유

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

4-L

vector를 이용할 시 시간초과 문제발생

298

amenable

작성한 질문수 7

0

안녕하세요.

해당 문제를 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();		
	}
}

C++ 코테 준비 같이 해요!

답변 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