글 읽기 - 이 알고리즘 시간 복잡도가 많이 큰가요?

injoon2018 5년 전 0

저는 이 알고리즘이 데이터가 N 개인 경우

입력을 받는데 O(N) 그리고 인덱스를 1부터 100000까지 검사하면 선형이니

O(N+100000) 즉 O(N)일 줄 알앗는데 시간초과가 나네요

#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <vector>
using namespace std;

long long int cnt[1000001];
int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	int num;
	cin >> num;
	long long int temp;
	long long int lartemp = 0;
	for(int k=0; k<num;k++)
	{
		cin >> temp;
		if (temp > lartemp)
			lartemp = temp;
		cnt[temp]++;
	}
	long long int largest = cnt[1];
	int index=1;
	for(int i = 2; i <= lartemp; i++)
	{
		if (largest < cnt[i])
		{
			largest = cnt[i];
			index = i;
		}
	}
	cout << index << "\n";
	system("pause");
	return 0;
}

windflower 5년 전 1

두번째 반복문에서 lartemp번 반복을 하시는데 최악의 조건에서 lartemp는 2^62까지 커질 수 있으니 시간초과가 납니다

injoon2018 5년 전 0

그렇네요 ㅎㅎ 감사합니다

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

문제

문제

출처

ICPC

이 알고리즘 시간 복잡도가 많이 큰가요?

injoon2018 5년 전 0

windflower 5년 전 1

injoon2018 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말