글 읽기 - 시간초과가 뜹니다... (c++)

dlgusrb3456 2년 전 0

논리는 잘 맞게 짠듯 합니다.

하지만 시간 초과가 뜹니다.

시간 복잡도를 더 줄일 수 있는 다른 논리가 있을까요?

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
int main(){
    map<int, int> map1;
	int max = 0;
	int counts = 0;
	int basckets, range;
	cin >> basckets >> range;
	for (int i = 0; i < basckets; i++) {
		int icecounts, icespot;
		cin >> icecounts >> icespot;
		map1.insert(pair<int, long long>(icespot, icecounts));
	}
	for (auto it = map1.begin(); it != map1.end(); it++) {
		for (auto iter =it; iter != map1.end(); iter++) {
			if (((*it).first) + (range*2) >= (*iter).first) {
				counts += (*iter).second;
			}
			else {
				break;
			}
		}
		if (max < counts) {
			max = counts;
		}
		counts = 0;
	}
	cout << max;
}

zigui 2년 전 0

이 코드의 시간복잡도는 N²인 것 같습니다.

19번째 반복문이 모든 원소를 순회하고, 20번째 반복문이 (break에 걸리지 않는다면) 나머지 원소를 순회하여 총 O(N²)의 시간복잡도를 가집니다.

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

문제

문제

출처

ICPC

시간초과가 뜹니다... (c++)

dlgusrb3456 2년 전 0

zigui 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말