글 읽기 - nlogn 인데 시간초과

dn1016 5년 전 0

입력값 하나 하나씩 읽어올때마다

바이너리 서치로 넣어줄 곳을 찾고,

넣어줄 곳의 위치에 따라 bubble 해야할 횟수를 알 수 있다는 점을 이용했는데

n log n 인데 시간초과가 나오네요

아예 새로운 접근이 필요한걸까요?

#include <iostream>
#include <vector>
#include <queue>

using namespace std;


vector<int> v;
int binary_search(int input)
{
	int t;
	int min = 0;
	int max = v.size() - 1;
	while (true)
	{
		t = (min + max) / 2;
		// cout << t << endl;
		if (input < v[t])
			max = t - 1;
		else
			min = t + 1;
		if (max - min <= 1)
		{
			return min;
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int N;
	int temp1, temp2;
	int ans = 0;
	int current_length = 0;
	cin >> N;
	cin >> temp1;
	v.push_back(temp1);
	for (int i = 0; i < N - 1; i++)
	{
		scanf("%d", &temp1);
		temp2 = binary_search(temp1);
		ans = ans + (v.size() - temp2);
		// cout << (v.size() - temp2) << endl;
		v.insert(v.begin() + temp2, temp1);

	}
	
	cout << ans;

	return 0;
}

bupjae 5년 전 2

46번째 줄 insert 의 시간복잡도는 O(n) 입니다.

따라서 이 프로그램의 시간복잡도는 O(n^2) 입니다.

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

문제

문제

출처

ICPC

nlogn 인데 시간초과

dn1016 5년 전 0

bupjae 5년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말