글 읽기 - 시간초과.... 어떻게 수정해야될지 모르겟습니다.

hnryu 6년 전 0

어느부분에서 어떻게 줄여야 할지 잘 모르겠습니다... ㅜㅜ

조언주시면 감사하겠습니다.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

typedef struct _person {
	int age;
	char name[20];
	int idx;
}person;

int main(void) {

	int i, j, num;
	scanf("%d", &num);
	
	person *str = (person*)malloc(sizeof(person)*num);

	for (i = 0; i < num; i++)
	{
		scanf("%d %s", &str[i].age, &str[i].name);
		str[i].idx= i;
	}
	
	int buff_age, temp;
	char buff_name[20];

	for (i = 1; i < num; i++)
	{
		for (j = 0; j < num-i; j++) {
			if (str[j].age> str[j + 1].age)
			{
				temp = str[j].idx;
				str[j].idx = str[j + 1].idx;
				str[j + 1].idx = j;
			}
			else if (str[j].age == str[j + 1].age)
			{
				if (strcmp(str[j].name, str[j + 1].name)>0) {
					temp = str[j].idx;
					str[j].idx = str[j + 1].idx;
					str[j + 1].idx = j;
				}
			}
		}
	}
	
	for (i = 0; i < num; i++) {
		strcpy(buff_name, str[str[i].idx].name);
		printf("%d, %s\n", str[str[i].idx].age, buff_name);
	}
	
}

codeonwort 6년 전 1

버블 정렬은 원소가 N개일 때 Θ(N²)의 시간이 걸려서 이 문제를 풀기에는 너무 느립니다.

시간복잡도가 O(NlogN)인 정렬 방법들을 찾아보세요.

혹은 직접 구현하지 않아도 C의 경우 <stdlib.h>의 qsort(), C++의 경우 <algorithm>의 sort()를 이용할 수 있습니다.

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

문제

문제

출처

ICPC

시간초과.... 어떻게 수정해야될지 모르겟습니다.

hnryu 6년 전 0

codeonwort 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말