C - [백준 10814] 나이순 정렬 (feat. qsort 함수 with 구조체)

참고 포스트

2025.01.13 - [Computer Science/알고리즘 문제] - C - [백준 11650] 좌표 정렬하기 (feat. qsort 함수 with 2차원 배열)

 

 

2025.01.11 - [Computer Science/C 언어] - C 표준 라이브러리 qsort() (feat. 퀵 정렬)

C 표준 라이브러리 qsort() (feat. 퀵 정렬)

2024.12.14 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 정렬 알고리즘 총 정리

[자료구조 & 알고리즘] 정렬 알고리즘 총 정리

 

 

 

 

BOJ 10814 나이순 정렬 ( https://www.acmicpc.net/problem/10814)

 

백준 10814번 문제는 회원의 나이를 기준으로 오름차순 정렬하는 문제입니다. 동일한 나이를 가진 경우에는 입력된 순서를 유지해야합니다.

---

입력 형식

1. 첫 번째 줄에 회원의 수 N이 주어진다. (1≤N≤100,000)
2. 다음 N개의 줄에는 회원의 나이와 이름이 공백으로 구분되어 주어진다.
   • 나이는 1≤ 나이 ≤ 200의 정수
   • 이름은 길이가 최대 100인 문자열

---

출력 형식

나이를 기준으로 오름차순 정렬된 결과를 출력한다.
나이가 같다면 입력 순서를 유지한다.

---

Checkpoint

 

qsort() 함수을 연습하는 시리즈 중 구조체를 이용하는 방법입니다. 2차원 배열과 qsort를 같이 사용했던

2025.01.13 - [Computer Science/알고리즘 문제] - C - [백준 11650] 좌표 정렬하기 (feat. qsort 함수 with 2차원 배열)

를 참고해주세요.

 

 해당 문제는 나이순으로 정렬하지만, 나이가 같은 경우 입력 순서 순으로 정렬을 해야합니다. 입력 순서를 기준으로 정렬해야한다는 것은 안정 정렬(Stable Sort)가 필요하다는 것을 의미합니다.안정 정렬(Stable Sort)란 정렬 후에도 동일한 값의 원소들이 정렬 이전의 순서를 유지하는 정렬 알고리즘입니다. 안정 정렬의 알고리즘에는 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort), 병합 정렬(Merge Sort)이 있습니다.

 

하지만 <stdlib.h> 헤더 파일의 qsort() 함수를 연습하고 있기 때문에 불안정 정렬(Unstable Sort)인 퀵 정렬(Quick Sort)를 사용해보겠습니다. 불안정 정렬인 만큼 정렬 이전의 순서를 따로 저장할 필요성이 있습니다. 이를 위해 멤버 구조체를 활용해 문제를 해결하였습니다 (= "qsort() + 구조체" ). 하단 코드는 해당 문제의 구조체 정의입니다.

typedef struct member {
    int index;      // 입력된 순서 저장
    char name[101]; // 이름
    int age;        // 나이
} member;

 

---

 

구현 코드

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

// 회원 정보를 저장할 구조체 정의
typedef struct member {
    int index;      // 입력된 순서 저장
    char name[101]; // 이름
    int age;        // 나이
} member;

// 정렬 기준 함수
int compare(const void *a, const void *b) {
    const member *mem1 = (const member *)a;
    const member *mem2 = (const member *)b;

    // 나이를 기준으로 정렬
    if (mem1->age != mem2->age) {
        return mem1->age - mem2->age; // 나이 오름차순
    }

    // 나이가 같으면 입력 순서(index) 기준으로 정렬
    return mem1->index - mem2->index;
}

member members[100000]; // 멤버 배열

int main() {
    int N = 0;
    scanf("%d", &N);

    // 회원 정보 입력
    for (int i = 0; i < N; i++) {
        int temp_age;
        char temp_name[101];

        // 나이와 이름 입력
        scanf("%d %s", &temp_age, temp_name);

        // 멤버 초기화
        members[i].age = temp_age;
        strcpy(members[i].name, temp_name);
        members[i].index = i; // 입력 순서 저장
    }

    // 정렬
    qsort(members, N, sizeof(member), compare);

    // 결과 출력
    for (int i = 0; i < N; i++) {
        printf("%d %s\n", members[i].age, members[i].name);
    }

    return 0;
}

 

1. 구조체 정의

회원 정보를 저장하기 위해 구조체 member를 정의합니다.
구조체는 세 가지 필드를 갖습니다:

• age: 회원의 나이
• name: 회원의 이름
• index: 입력된 순서(정렬 안정성을 위해 사용)

typedef struct member {
    int index;      // 입력된 순서 저장
    char name[101]; // 이름
    int age;        // 나이
} member;

2. 정렬 기준 함수

qsort를 사용하여 구조체 배열을 정렬합니다.
정렬 기준은 다음과 같습니다:

1. 나이 기준: age를 기준으로 오름차순 정렬
2. 입력 순서 유지: 나이가 같을 경우 index를 기준으로 정렬

int compare(const void *a, const void *b) {
    const member *mem1 = (const member *)a;
    const member *mem2 = (const member *)b;

    if (mem1->age != mem2->age) {
        return mem1->age - mem2->age; // 나이 오름차순
    }
    return mem1->index - mem2->index; // 입력 순서 유지
}

3. 정렬 및 출력

• 회원 정보를 입력받아 members 배열에 저장합니다.
• qsort를 사용해 정렬한 후 결과를 출력합니다.

qsort(members, N, sizeof(member), compare);

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

---

입력 예제

5
21 Junkyu
21 Dohyun
20 Sunyoung
21 Jinho
20 Alice

---

출력 예제

20 Sunyoung
20 Alice
21 Junkyu
21 Dohyun
21 Jinho

 

---

핵심 포인트

1. 안정 정렬 구현:
   입력 순서를 저장하고, 정렬 기준에 이를 반영하여 안정성을 확보합니다.
2. qsort 사용법:
   사용자 정의 정렬 기준 함수를 작성하여 정렬 기준을 명확히 정의합니다.
3. 구조체 활용:
   데이터를 구조적으로 관리하여 나이, 이름, 입력 순서를 효율적으로 처리합니다.

 

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.