글 읽기 - 시간 초과가 뜨는데 이 문제를 어떻게 해결해야 할까요?

testtest4 5년 전 0

시간 초과가 뜨네요. 저는 조건문으로 하나하나 검색하라고 하긴 했는데 다른 방법이 생각이 안 나네요.

다른 알고리즘을 사용해야 하는 건가요?

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

using namespace std;

class Student {
public:
	string name;
	int korean, english, math;
	Student(string noname = "noname", int a = 0, int b = 0, int c = 0)
		: name(noname), korean(a), english(b), math(c) {}

	void print() {
		cout << name << " " << korean << " " << english << " " << math << endl;;
	}
};

bool comparision(Student a, Student b) {
	if (a.korean > b.korean) {//국어가 큰경우 바꿈
		return true;
	}
	else if (a.korean == b.korean) {
		if (a.english < b.english) {//영어가 작은경우 바꿈
			return true;
		}
		else if (a.english == b.english) {
			if (a.math > b.math) {//수학이 큰경우
				return true;
			}
			else if (a.math == b.math) {
				return a.name < b.name;//문자열 사전순 바꿈
			}
			else return false;
		}
		else return false;
	}
	else return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	Student *student = new Student[100000];
	int n, korean, english, math;
	string stu_name;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> stu_name >> korean >> english >> math;

		Student temp(stu_name, korean, english, math);
		
		student[i] = temp;
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (comparision(student[i], student[j])) {
				Student temp = student[i];
				student[i] = student[j];
				student[j] = temp;
			}
		}
	}

	for (int i = 0; i < n; i++) cout << student[i].name << '\n';
}

djm03178 5년 전 1

지금 사용하신 정렬 방법은 버블 정렬로, O(N^2)의 시간복잡도를 가지는 정렬입니다.

O(NlogN)의 시간복잡도를 가지는 정렬들을 사용해야 합니다. 이에 해당하는 정렬로는 병합 정렬, 힙 정렬 등이 있습니다.

testtest4 5년 전 0

혹시 이런 정렬은 안되나요? 입력받을 때 정렬시키는 건데 이것도 시간복잡도가 버블 정렬과 비슷한가요?

for (int i = 0; i < n; i++) {
		cin >> stu_name >> korean >> english >> math;

		Student temp(stu_name, korean, english, math);

		student[i] = temp;

		for (int j = 0; j < i; j++) {
			if (comparision(student[i], student[j])) {
				Student temp = student[i];
				student[i] = student[j];
				student[j] = temp;
				break;
			}
		}
	}

djm03178 5년 전 1

마찬가지입니다. 입력을 한 번 받을 때마다 최대 현재까지의 원소 수만큼 swap을 수행해야 하기 때문에, 여전히 O(N^2)입니다.

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

문제

문제

출처

ICPC

시간 초과가 뜨는데 이 문제를 어떻게 해결해야 할까요?

testtest4 5년 전 0

djm03178 5년 전 1

testtest4 5년 전 0

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말