C - [백준 11650] 좌표 정렬하기 (feat. qsort 함수 with 2차원 배열)

참고 포스트

 

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

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

 

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

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

 

BOJ 11650  좌표정리하기

문제 정의

• 입력값: N개의 2차원 배열 요소가 주어집니다. 각 요소는 두 개의 정수로 구성됩니다.
• 정렬 조건:
  1. 첫 번째 열(첫 번째 정수)을 기준으로 오름차순 정렬합니다.
  2. 첫 번째 열의 값이 같은 경우, 두 번째 열(두 번째 정수)을 기준으로 오름차순 정렬합니다.
• 목표: 정렬된 2차원 배열을 출력합니다.

---

Checkpoint - qsort()함수로 2차원 배열 정렬하기

이번 포스팅에서는 qsort 함수를 사용하여 2차원 배열을 정렬하는 방법을 알아보겠습니다. 주어진 2차원 배열에서 특정 열을 기준으로 정렬하고, 동일한 값일 경우 다른 열을 기준으로 정렬하는 방식에 대해 설명합니다.

 

qsort 함수 자체는  C언어 표준 라이브러리 <stdlib.h>에 포함된 함수로, 불러다가 쓰기만 하면 되기 때문에 매게변수만 맞춰주면 어려움이 없으나, qsort 함수에 필요한 매개변수인 비교함수(보톰 compare로 명칭)를 어떻게 설계하는지가 중요합니다.

qsort(배열, 배열 크기, 배열 요소 크기, 비교 함수);

 

기본적으로 compare 함수는 void 포인터 함수이기 때문에 비교하려는 변수의 자료형에 맞춰 재선언후, 문제의 요구사항에 맞게 비교해야합니다.

 

아래 compare 함수는 해당 문제의 비교 함수입니다. 현재 비교해야하는 것이 int형 2차원 배열이기 때문에 해당 사항에 맞춰 rowA, rowB를 선언하고 있으며, 첫번째 열, 즉 x 좌표를 기준으로 정렬한 후, x좌표가 동일 할 경우 y 좌표를 기준으로 정렬을 하는 프로세스를 확인할 수 있습니다. 

int compare(const void *a, const void *b) {
    const int *rowA = (const int *)a;
    const int *rowB = (const int *)b;

    // 첫 번째 열(arry[][0])을 기준으로 정렬
    if (rowA[0] != rowB[0]) {
        return rowA[0] - rowB[0]; // 오름차순
    }

    // 첫 번째 값이 같으면 두 번째 열(arry[][1])을 기준으로 정렬
    return rowA[1] - rowB[1]; // 오름차순
}

---

구현 코드

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

int N = 0;
int arry[100000][2];

// 비교 함수
int compare(const void *a, const void *b) {
    const int *rowA = (const int *)a;
    const int *rowB = (const int *)b;

    // 첫 번째 열(arry[][0])을 기준으로 정렬
    if (rowA[0] != rowB[0]) {
        return rowA[0] - rowB[0]; // 오름차순
    }

    // 첫 번째 값이 같으면 두 번째 열(arry[][1])을 기준으로 정렬
    return rowA[1] - rowB[1]; // 오름차순
}

int main() {
    // 입력 받기
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d %d", &arry[i][0], &arry[i][1]);
    }

    // 정렬
    qsort(arry, N, sizeof(arry[0]), compare);

    // 결과 출력
    for (int i = 0; i < N; i++) {
        printf("%d %d\n", arry[i][0], arry[i][1]);
    }

    return 0;
}

 

구조체도 해당 qsort 알고리즘에서 활용할 수 있는데, 이에 관한 내용은 다음 포스트를 통해 이어가겠습니다.

---

코드 설명

1. qsort 함수 사용
   • qsort는 C언어 표준 라이브러리 <stdlib.h>에 포함된 함수로, 배열을 정렬할 때 사용됩니다.
   • 호출 형태:

     qsort(배열, 배열 크기, 배열 요소 크기, 비교 함수);
     

2. 비교 함수 (compare)
   • compare 함수는 qsort가 두 요소를 비교할 때 호출합니다.
   • 입력: 정렬할 두 배열의 요소 포인터(const void *a, const void *b).
   • 동작:
     1. 각 포인터를 2차원 배열의 한 행으로 캐스팅합니다.
     2. 첫 번째 열(열 0)을 비교하여 정렬합니다.
     3. 첫 번째 열 값이 같으면 두 번째 열(열 1)을 비교합니다.
3. 정렬 기준
   • return rowA[0] - rowB[0]: 첫 번째 열을 기준으로 오름차순 정렬.
   • return rowA[1] - rowB[1]: 첫 번째 열 값이 같을 때 두 번째 열 기준으로 오름차순 정렬.
4. 입출력 처리
   • 입력: 2차원 배열의 각 요소를 scanf로 읽어옵니다.
   • 출력: 정렬된 배열을 printf로 출력합니다.

---

동작 예제

입력:

5
3 4
1 2
3 2
5 1
1 3

정렬 과정:

1. 첫 번째 열(열 0)을 기준으로 오름차순 정렬.
2. 첫 번째 열 값이 같은 경우, 두 번째 열(열 1)을 기준으로 오름차순 정렬.

출력:

1 2
1 3
3 2
3 4
5 1

---

시간 복잡도

1. 정렬 복잡도:
   • qsort는 평균적으로 O(log⁡N)의 시간 복잡도를 가집니다.
2. 입력 크기 제한:
   • 최대 N=100,000개의 요소를 처리할 수 있습니다.

 

 

---

 

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