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

bangbadak 4년 전 0

이중 반복문도 안 썼는데 왜 시간초과가 나나요?

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(void)
{
	bool all_0 = 1;
	int N, com, i, j, m;
	cin >> N;
	vector<int> s;
	for (i = 0; i < N; i++)
	{
		cin >> com;
		all_0 = s.size() ? 0 : 1;
		if (com) //com > 0
		{
			all_0 = 1;
			s.push_back(com);
		}
		else //com == 0
		{
			if (s.size() < 2)
			{
				if (all_0)
					cout << "0" << '\n';
				else
				{
					cout << s[0] << '\n';
					s.erase(s.begin());
					all_0 = 1;
				}
			}
			else
			{
				m = *min_element(s.begin(), s.end());
				cout << m << '\n';
				vector<int>::iterator it = find(s.begin(), s.end(), m);
				s.erase(it);
			}
		}
	}
}

bangbadak 4년 전 0

ios_base::sync_with_stdio(false); cin.tie(NULL);

추가했더니 맞았네요..

djm03178 4년 전 3

그 외에도 매우 비효율적인 부분들이 있어 O(n^2)이지만, 너무 빠른 연산들이라서 통과될 뿐입니다.

1. vector의 임의의 위치의 원소를 지우는 것은 뒤에 있는 원소들을 전부 한 칸씩 당겨오게 만드므로 길이에 비례하는 시간이 걸립니다.

2. min_element 역시 벡터 전체를 순회하면서 모든 원소들을 확인하고 그 중 최소를 뽑아야 하므로 길이에 비례하는 시간이 걸립니다.

단순히 겉으로 보기에 이중 루프가 없다고 해서 O(n)인 것이 아니고, 라이브러리 함수들도 다 제각각 시간복잡도를 가지고 있다는 점을 명심하세요.

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

문제

문제

출처

ICPC

시간초과가 나는 이유를 모르겠습니다

bangbadak 4년 전 0

bangbadak 4년 전 0

djm03178 4년 전 3

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말