글 읽기 - 7785 시간초과 이유를 모르겠습니다

kiasu93 6년 전 0

leave가 나오면 벡터에서 해당 이름인 사람(원소) 지우고 지우고 남은 공간을 지워주는 식으로 했는데

시간초과가 뜨네요.. 왜그런지 알수있을까요??

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

int main() {
	vector<string>v;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		string temp1;
		string temp2;
		cin >> temp1 >> temp2;

		if (temp2 == "leave") {
			v.erase(remove(v.begin(), v.end(), temp1), v.end());
		}
		else {
			v.push_back(temp1);
		}
	}
	::sort(v.begin(), v.end(), greater<string>());
	for (int i = 0; i < v.size(); i++)
		cout << v[i] << "\n";
	return 0;
}

djm03178 6년 전 1

벡터에서 원소를 찾고, 지우고, 뒤의 원소를 하나씩 당겨오는 것이 모두 O(n)입니다. 따라서 총 수행 시간이 O(n^2)으로 압도적으로 시간이 부족합니다.

kiasu93 6년 전 0

원소를 찾고, 지우고, 하나씩 당겨오는 각각의 모든 과정이 개별적으로 O(n)인가요?? 그렇게되면 for문 까지 O(n^4)이 되는건가요?

djm03178 6년 전 0

개별적으로 O(n)이니, 순차적으로 실행한 총합도 O(n)입니다. 이 전부를 O(n)번 반복하니 O(n^2)입니다.

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

문제

문제

출처

ICPC

7785 시간초과 이유를 모르겠습니다

kiasu93 6년 전 0

djm03178 6년 전 1

kiasu93 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말