[C] 백준 10814번 나이순 정렬

링크
https://www.acmicpc.net/problem/10814

문제

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄부터 N개의 줄에는 각 회원의 나이와 이름이 공백으로 구분되어 주어진다. 나이는 1보다 크거나 같으며, 200보다 작거나 같은 정수이고, 이름은 알파벳 대소문자로 이루어져 있고, 길이가 100보다 작거나 같은 문자열이다. 입력은 가입한 순서로 주어진다.

출력

첫째 줄부터 총 N개의 줄에 걸쳐 온라인 저지 회원을 나이 순, 나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다.

예제 입력 1

3
21 Junkyu
21 Dohyun
20 Sunyoung

예제 출력 1

20 Sunyoung
21 Junkyu
21 Dohyun

아이디어 스케치

• 입력으로 나이와 이름이 들어오고 출력은 나이가 적은 순, 나이가 같을 때는 먼저 가입한 순으로 출력된다.
• 정렬하기 위해서는 나이, 이름, 가입한 순서(인덱스)가 필요하다.
• 나이와 이름, 인덱스 번호는 서로 짝지어져야 하므로 구조체를 이용하면 수월하다.
• 구조체에 이름과 나이, 가입한 순서(인덱스 번호)를 요소로 하여 하나의 Person을 만든다.
• 정렬은 퀵 정렬을 이용한다.

코드 분할 설명

typedef struct
{
    int age;
    int idx;
    char name[101];
}person;        //이름과 인덱스 나이를 가지는 구조체 생성

• 나이(age), 가입한 순서(idx), 이름(name)을 하나의 구조체 Person으로 선언해준다.

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

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

• 인원수 n을 입력 받은 후 person구조체형으로 메모리를 동적할당한다.
• 나이와 이름을 입력받은 후 가입한 순서를 식별하기 위해 idx에 현재 순서를 의미하는 i를 저장한다.

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

• 퀵 정렬을 수행한다.

int compare(const void* first, const void* second)
{
    person* a = (person*)first;
    person* b = (person*)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;
}

• 퀵 정렬에 사용되는 compare 함수이다.
• 문제에서는 정렬 1순위를 나이가 적은순으로, 2순위가 가입을 먼저한 순(idx가 적은순)이다.
• Compare 함수에서는 먼저 나이를 오름차순 정렬을 하고 나이가 같을 때는 인덱스를 오름차순으로 정렬하였다. 이때 구조체는 하나의 객체로 여겨지므로 각 사람의 나이와 인덱스 이름은 함께 움직인다.

전체 코드

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

typedef struct
{
    int age;
    int idx;
    char name[101];
}person;        //이름과 인덱스 나이를 가지는 구조체 생성

int compare(const void* first, const void* second)
{
    person* a = (person*)first;
    person* b = (person*)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;
    person* list;

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

    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);

    printf("\n");

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

    free(list);

    return 0;




}

제출 결과