글 읽기 - 시간초과....

tjdtldud95 2년 전 0

저기 while쪽에서 O(n2)이기때문에 자꾸 시간초과가 나는걸까요?>..

#include<iostream>
#include<algorithm>

using namespace std;

int tmp[1000000];
int arr[1000000] = { 0 };
int main()
{
	int n, i, j, key;

	cin >> n;

	for (i = 0;i < n;i++)
	{
		cin >> tmp[i];
		arr[i] = tmp[i];
	}
	
	sort(tmp, tmp + n);

	j = 0;
	key = 0;
	while (key <n)
	{
		bool change = false;
		for (i = 0;i < n;i++)
		{
			if (arr[i] == tmp[key])
			{
				arr[i] = j;
				change = true;
			}
		}
		if (change) j++;

		key++;
		if (tmp[key - 1] == tmp[key])
			key++;
		
	}

	for (i = 0;i < n;i++)
	{
		cout << arr[i] << " ";
	}

	return 0;

}

djm03178 2년 전 1

맞습니다. O(N^2)이 되지 않게 더 빠른 방법을 생각해 보세요.

tjdtldud95 2년 전 0

하나만 더 물어봐도 괜찮을까요?? 저기 sort까지는 시간초과에 문제가 없을까요??

djm03178 2년 전 0

네. sort까지는 많아야 0.5초면 돌 것 같습니다. sort보다도 입력이 대부분의 시간을 차지합니다.

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

문제

문제

출처

ICPC

시간초과....

tjdtldud95 2년 전 0

djm03178 2년 전 1

tjdtldud95 2년 전 0

djm03178 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말