글 읽기 - 국영수 문제 시간초과가 뜨네요 어떻게 해결해야 할까요?

ook505 6년 전 0

구조체를 만들고 선택 정렬과 버블 정렬을 이용하여 문제를 풀었는데 시간 초과가 뜨네요ㅠ

코드가 불필요하게 긴 느낌도 조금 드는데 이 문제를 어떻게 해결해야 할까요?

#include <stdio.h>
#include <string.h>
typedef struct {
	char name[11];
	int kor;
	int eng;
	int math;
} student;
void swap(student *, student *);
int main()
{
	int i, j, n, max;
	student *score;
	scanf("%d", &n);
	score = (student *)malloc(n * sizeof(student));
	for (i = 0; i < n; i++) {
		scanf("%s %d %d %d", score[i].name, &score[i].kor, &score[i].eng, 
			&score[i].math);
	}
	for (i = 0; i < n - 1; i++) { // 선택 정렬을 이용해 국어 내림차순 정리
		max = i;
		for (j = i + 1; j < n; j++) {
			if (score[j].kor > score[max].kor)
				max = j;
		}
		swap(&score[i], &score[max]);
	}
	for (i = 0; i < n - 1; i++) { // 버블 정렬을 이용해 영어 오름차순 정리
		for (j = 0; j < n - 1 - i; j++) {
			if (score[j].kor == score[j + 1].kor && score[j].eng > score[j + 1].eng) {
				swap(&score[j], &score[j + 1]);
			}
		}
	}
	for (i = 0; i < n - 1; i++) { // 버블 정렬을 이용해 수학 내림차순 정리
		for (j = 0; j < n - 1 - i; j++) {
			if (score[j].kor == score[j + 1].kor && score[j].eng == score[j + 1].eng &&
				score[j].math < score[j + 1].math) {
				swap(&score[j], &score[j + 1]);
			}
		}
	}
	for (i = 0; i < n - 1; i++) { // 버블 정렬을 이용해 문자열 사전순으로 정리
		for (j = 0; j < n - 1 - i; j++) {
			if (score[j].kor == score[j + 1].kor && score[j].eng == score[j + 1].eng &&
				score[j].math == score[j + 1].math && strcmp(score[j].name, score[j + 1].name) > 0) {
				swap(&score[j], &score[j + 1]);
			}
		}
	}
	for (i = 0; i < n; i++)
		printf("%s\n", score[i].name);
}
void swap(student *p, student *q)
{
	student temp = *p;
	*p = *q;
	*q = temp;
}

bupjae 6년 전 1

선택정렬이나 거품정렬은 이 문제에서 주어지는 규모의 데이터를 처리하기에는 너무 느립니다.

좀 더 빠른 정렬 방법을 사용하셔야 합니다.

ook505 6년 전 0

네 감사합니다ㅎㅎ 퀵 정렬 이용해서 한 번 해보겠습니다.

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

문제

문제

출처

ICPC

국영수 문제 시간초과가 뜨네요 어떻게 해결해야 할까요?

ook505 6년 전 0

bupjae 6년 전 1

ook505 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말