[백준/11651/C언어] 좌표 정렬하기 2 _ 풀이

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

11651번: 좌표 정렬하기 2

---

풀이

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

// 구조체 변수 xy 선언
typedef struct{
    int x;
    int y;
} xy;

//  compare함수 선언
int compare(const void* first, const void* second);

int main(){
    int n;
    scanf("%d",&n);
    // cdn이라는 배열을 n개만큼 동적 할당
    xy* cdn = (xy*)malloc(n*sizeof(xy));
    
    // n번 반복
    for(int i=0;i<n;i++)
        // cnd[i]의 x,y에 입력값 할당
        scanf("%d %d",&cdn[i].x ,&cdn[i].y);
    
    // qsort로 정렬
    qsort(cdn, n, sizeof(xy), compare);

    // 정렬된 x와 y를 출력
    for( int i=0;i<n;i++) 
        printf("%d %d\n", cdn[i].x, cdn[i].y);
    
    free(cdn);
    return 0;
}

// compare 함수 정의
int compare(const void* first, const void* second){
    // a, b라는 구조체 첫항, 두번째 항의 주소 참조 
    xy a = *(xy*)first;
    xy b = *(xy*)second;
    // 오름차순 정리
    // 첫항의 y가 둘째항의 y보다 작을때 냅둠
    if(a.y<b.y) return -1;
    // 첫항의 y가 둘째항의 y보다 클때 서로 바꿈
    else if(a.y>b.y) return 1;
    // 첫항 둘째항 y 모두 같다면
    else {
        // 첫항의 x가 둘째항의 x보다 작을때 냅둠
        if(a.x<b.x) return -1;
        // 첫항의 x가 둘째항의 x보다 클때 서로 바꿈
        else if(a.x>b.x) return 1;
        // // 첫항의 x가 둘째항의 x랑 같을때 0
        else return 0;
        return 0;
    }
    // 오름차순 정렬 완료
}

핵심은

'표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램'

으로 작성하는 것이다.

 

1. y좌표가 같을때 x좌표도 증가해야 한다

= y정렬을 멈추고 x정렬을 시도해야함

= 구조체 선언을 통해 간단하게 접근해서 정렬 가능하다.

2. qsort 사용 O(n^2)

3. qsort 내에서 y정렬 중 x정렬 코드 구현

4. 정렬된 배열 출력