글 읽기 - C++ 시간초과 뜹니다

av3rs1on 2년 전 0

퀵정렬보다 병합정렬이 좋다해서 사용해봤는데 시간초과가 뜨네요 어디서 시간 많이 잡아먹는건가요??

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

class Data {
public :
	int num;
	int frequency;
	Data(int n=0, int frequncy =1) {
		num = n;
		frequency = frequncy;
	}
};

void merge(vector<Data>& v, int s, int e, int m) {
	int i = s;
	int j = m + 1;
	int a = 0;
	vector<Data> tmp;

	while (i <= m && j <= e) {
		if (v[i].num <= v[j].num)
			tmp.push_back(v[i++]);
		else if (v[i].num > v[j].num)
			tmp.push_back(v[j++]);
	}
	while (i <= m)
		tmp.push_back(v[i++]);
	while (j <= e)
		tmp.push_back(v[j++]);
	for (int k = s; k <= e; k++) {
		v[k] = tmp[a++];
	}
}
void mergesort(vector<Data>& v, int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;
		mergesort(v, left, mid);
		mergesort(v, mid + 1, right);
		merge(v, left, right, mid);
	}
}
int main() {
	int n;
	cin >> n;
	vector<Data> arr;
	vector<Data> tmp;
	vector<Data>::iterator it;
	Data data;
	int m;
	float avg = 0;
	for (int i = 0; i < n; i++) {
		cin >> m; 
		avg += m;
		data = Data(m, 1);
		arr.push_back(data);
	}
	mergesort(arr, 0, n-1);
	tmp = arr;
	int c = n-1;

	for (it = arr.begin(); it != arr.end(); it++) {
		if (it != arr.begin()){
			if (it->num == (it - 1)->num) {
				(it - 1)->frequency++;
				arr.erase(it--);
				c--;
			}
		}
	}
	int maxValue = 0;
	int list[2] = { 0, 0 };
	bool once = true;

	for (int i = 0; i < c+1; i++) {
		if (maxValue < arr[i].frequency) {
			maxValue = arr[i].frequency;
			list[0] = arr[i].num;
			once = true;
		}
		else if (maxValue == arr[i].frequency) {
			if (once) {
				list[1] = arr[i].num;
				once = false;
			}
		}
	}
	if (once) {
		list[1] = list[0];
	}
	cout << '\n';
	cout << round(avg/n) << '\n';
	cout << tmp.at(n / 2).num << '\n';
	cout << list[1] << '\n';
	cout << arr.at(c).num - arr.at(0).num << '\n';

	return 0;
}

ckdgus2482 2년 전 0

중앙값을 위해 입력받은 데이터를 나이브하게 소팅하는 풀이는 아마 의도된 풀이가 아닐 것입니다.

절대값이 4000을 넘지 않는다는 조건을 보고 다시 한번 생각해보시면 좋을 것 같습니다.

그리고 그것과 별개로 벡터의 중간에 있는 데이터를 erase하는 것은 굉장히 비효율적입니다. 벡터는 랜덤 액세스가 가능해야하기 때문에 모든 항목들이 메모리상에 연속으로 위치해야하는데 중간에서 삭제하면 그 뒤에 있는 애들을 전부 한칸씩 당겨서 복사해와야한다는 의미죠. 그런 동작이 필요하다면 list를 사용해야합니다.

av3rs1on 2년 전 0

벡터 중간의 erase가 비효율적이라는 건 처음 알았네요 감사합니다.

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

문제

문제

출처

ICPC

C++ 시간초과 뜹니다

av3rs1on 2년 전 0

ckdgus2482 2년 전 0

av3rs1on 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말