글 읽기 - (C++)vector를 쓰면 시간이 오래걸리는건가요?

legendmic2 5년 전 0

이 코드로 시간초과나서 다른방법으로 풀어서 맞았습니다 나오긴했는데,,

vector쓰는재미에 빠져서 요새 계속 vector로 코드짜보는데요, 시간초과가 뜨는 경우가 있더라구요

어떤 이유로 시간초과가 나는지 궁금합니다!

#include <iostream>
#include <vector>

using namespace std;


int main()
{
	vector<int> card;
	int n = 0;
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		card.push_back(i); // 1부터 n까지의 수 삽입
	}

	while (card.size() != 1)
	{
		card.erase(card.begin()); // 맨 앞 숫자 삭제
		card.push_back(card.at(0)); // 맨 앞 숫자를 맨 뒤에 추가
		card.erase(card.begin()); // 맨 앞 숫자를 삭제
	}
	cout << card[0];
}

kipa00 5년 전 2

vector::erase(vector::begin()) 연산은 container의 size에 비례하는 시간이 걸립니다. reference

djm03178 5년 전 5

STL은 시간복잡도의 한계를 넘어설 수 있는 마법이 아니라, 익히 알려진 자료구조를 '잘' 구현한 라이브러리에 불과합니다. 랜덤 액세스를 항상 O(1)에 할 수 있다는 건 벡터는 평범한 동적 배열의 형태라는 뜻이고, 배열의 임의의 원소를 제거하고도 인덱스를 그대로 유지하려면 뒤에 있는 원소들을 전부 앞으로 당겨오는 수밖에 없습니다.

벡터 뿐만 아니라 STL의 어떤 기능을 쓰더라도, 각각 어떤 자료구조를 사용하고 그에 대한 연산들이 어떤 시간복잡도를 가지는지 숙지하고 사용하는 것이 좋습니다.