글 읽기 - vector 속도 개선 가능한가요?

plan222 3년 전 0

시간복잡도에 비해 너무 오래걸리는 거같아 벡터를 배열로 바꿔봤더니 수행속도가 약 3000ms -> 150ms 로 줄었네요.

push_back이 오래걸린다는 건 알고있었지만 조회하는 곳에서도 시간을 많이 잡아먹는것 같아요.

벡터의 크키가 크고 많이 조회해야한다면 무조건 배열로 바꾸는게 답인가요??

처음에 짰던 코드 올려봅니다.

23, 35~37, 79~89 줄만 봐주시면 될 것 같아요.

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <time.h>

#define MAX(A,B) A>B?A:B
#define MIN(A,B) A<B?A:B
#define forn(i,n) for(long long i=0;i<n;i++)
#define ll long long
ll gcd(ll a, ll b) { return a % b ? gcd(b, a % b) : b; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a, b); }
ll wasdX[4] = { 1,0,-1,0 }; ll wasdY[4] = { 0,1,0,-1 };
using namespace std;

ll prefixSum[100001];
bool notPrime[100001];
bool win[100001];  //i에서 이번턴에 차례인 사람이 이김
vector<ll> v;

void findPrime()
{
	for (int i = 2; i < sqrt(100001)+1; i++)
	{
		if (notPrime[i])
			continue;
		for (int j = 2*i; j < 100001; j += i)
			notPrime[j] = true;
	}
	
	for (int i = 2; i < 100001; i++)
		if (!notPrime[i])
			v.push_back(i);
}
void solve()
{
	ll A, k;
	cin >> A >> k;
	ll cnt = 0, x = A + 1- k;
	/*for (int i = A; i >= A + 1 - k; i--)
	{
		if (!win[i])
			cnt++;
	}*/
	cnt = prefixSum[A] - prefixSum[A - k];
	ll maxCnt = cnt, minX = x;
	x--;
	while (x >= 2)
	{
		if (!win[x + k])
			cnt--;
		if (!win[x])
			cnt++;
		if (cnt >= maxCnt)
		{
			maxCnt = cnt;
			minX = x;
		}
		x--;
	}
	cout << maxCnt << " " << minX << "\n";
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll t = 1;
	cin >> t;

	clock_t start, end;
	start = clock();
	findPrime();
	int vsize = v.size();
	for (int i = 0; i < 100001; i++)
	{
		if (win[i])
			continue;
		for (int j = 0; j < vsize; j++)
		{
			if (i + v[j] > 100000)
				break;
			win[i + v[j]] = true;
		}
	}
	
	end = clock();
	prefixSum[0] = 1;
	for (int i = 1; i < 100001; i++) //prefix sum
	{
		prefixSum[i] = prefixSum[i - 1] + !win[i];
	}
	cout << (double)(end - start);
	//cout << '\n' << cnt;
	while (t--)
	{
		solve();
	}

}

herdson 3년 전 0

emplace_back을 써보시거나 벡터를 선언할 때 크기를 초기화 해주면 개선될 것 같습니다.

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

문제

문제

출처

ICPC

vector 속도 개선 가능한가요?

plan222 3년 전 0

herdson 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말