[C] 백준 | 10814번 코드 - 나이순 정렬

>문제

> 핵심

구조체 정렬

 

>풀이과정

구조체로 나이, 이름, 인덱스(가입순번)을 묶어 입력받은 다음, qsort를 이용해 정렬했다.

 

삽입정렬이나 선택정렬으로 짰으면 이중반복문을 돌면서 두가지 조건을 만족하는지 고려하면서 짜야해서 조금 생각이 많이 필요했을 텐데 qsort 함수는 그런게 필요없으니까 너무 쉽고 편하다.

 

그래도 내장함수만 쓰면 그러니까 선택정렬로 짜봤는데 시간초과가 떴다.

선택정렬은 O(n^2) 의 시간이 걸려서 그런 것 같다.

답은 맞게 나오니 뭐 공부한 셈 치자

>깨달은점

qsort는 빛이다

 

>코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct
{
	int age;
	int idx;
	char name[101];
}member;

int compare(const void* first, const void* second)
{
	member* a = (member*)first;
	member* b = (member*)second;

	if (a->age < b->age)
		return -1;
	else if (a->age > b->age)
		return 1;
	else
	{
		if (a->idx < b->idx)
			return -1;
		else
			return 1;
	}
	return 0;
}

int main()
{
	int i, n;
	member* list;

	scanf("%d", &n);
	list = (member*)malloc(n * sizeof(member));

	for (i = 0; i < n; i++)
	{
		scanf(" %d %s", &list[i].age, list[i].name);
		list[i].idx = i;
	}

	qsort(list, n, sizeof(list[0]), compare);

	for (i = 0; i < n; i++)
	{
		printf("%d %s\n", list[i].age, list[i].name);
	}

	return 0;
}

 

선택정렬 버전(시간초과)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct
{
	int age;
	int idx;
	char name[101];
}member;

void selection_sort(member* list, int n)
{
	int least;
	member tmp;

	for (int i = 0; i < n - 1; i++)
	{
		least = i;
		for (int j = i + 1; j < n; j++)
		{
			if (list[j].age < list[least].age)
			{
				least = j;
			}
			else if (list[j].age == list[least].age)
			{
				if (list[j].idx < list[least].idx)
					least = j;
			}
		}
		if (i != least)
		{
			tmp = list[least];
			list[least] = list[i];
			list[i] = tmp;
		}
	}
}

int main()
{
	int i, n;
	member* list;

	scanf("%d", &n);
	list = (member*)malloc(n * sizeof(member));

	for (i = 0; i < n; i++)
	{
		scanf(" %d %s", &list[i].age, list[i].name);
		list[i].idx = i;
	}

	selection_sort(list, n);

	for (i = 0; i < n; i++)
	{
		printf("%d %s\n", list[i].age, list[i].name);
	}

	return 0;
}