백준 알고리즘 11650번 : 좌표 정렬하기

문제 링크

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

제한

문제

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.

출력

첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.

예제 입력 및 출력

풀이

1. x,y를 정렬하기 쉽게 정렬하기 위해서 구조체를 사용하였다.

2. 테스트 케이스 변수를 선언하고 동적할당을 활용해서 그만큼의 메모리를 할당받고 x와 y값을 입력 받는다.

3. qsort를 활용하기 위해서 compare함수를 정의한다.

4. 문제에서 x의 값이 증가하게 정렬하고 x의 값이 같을 때는 y값이 증가하는 방향으로 정렬하라고 하였으니 compare함수에서 void 값 a,b를 받고 그것을 Point 형식으로 역참조해서 구조체 A와 B를 선언한다.

5. 조건문을 활용해서 A.x > B.x이면 1(오름차순)정렬,
   A.x == B.x이면 y의 값이 증가하도록 하고 그게 아닐 시 -1을 반환하도록한다.

6. 정렬된 결과를 출력한다.

풀이 코드

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

typedef struct {
  int x;
  int y;
} Point;

int compare(const void *a, const void *b){
  Point A = *(Point *)a;
  Point B = *(Point *)b;
  if(A.x > B.x){
    return 1;
  }
  else if(A.x == B.x){
    if(A.y > B.y){
      return 1;
    }
    else{
      return -1;
    }
  }
  return -1;
}

int main(){
  int test;
  scanf("%d",&test);
  Point *arr;
  arr = (Point *)malloc(sizeof(Point) * test);
  for(int i = 0; i < test; i++){
    scanf("%d %d",&arr[i].x,&arr[i].y);
  }
  qsort(arr,test,sizeof(Point),compare);
  for(int i = 0; i < test; i++){
    printf("%d %d\n",arr[i].x,arr[i].y); 
  }
  free(arr);
  return 0;
}

복기

퀵 정렬을 연습하기 좋은 문제였다고 생각한다.
구현에 어려운 점은 딱히 없었다.