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

 

링크

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

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;




}

 

 

 

 

 

 

 

제출 결과

---