[백준] 11650(좌표 정렬하기) c언어

문제

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

입력

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

출력

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

 

---

 

> 오름차순으로 정렬하기
x기준으로 y도 같이 정렬한다. 

 

1) 처음 생각한 알고리즘 - 수작업

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

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

  int *x, *y; 
  x = calloc(n, sizeof(int));
  y = calloc(n, sizeof(int));

  for(int i=0; i<n; i++) {
    scanf("%d %d", &x[i], &y[i]);
  }

  for(int j=0; j<n; j++) {
    for(int i=1; i<n; i++) {
      if(x[i-1] > x[i]) {
        temp = x[i-1];
        x[i-1] = x[i];
        x[i] = temp;

        temp = y[i-1];
        y[i-1] = y[i];
        y[i] = temp;
      }   
    }
  }

  for(int j=0; j<n; j++) {
    for(int i=1; i<n; i++) {
      if(x[i-1] == x[i]) {
        if(y[i-1] > y[i]) {
          temp = y[i-1];
          y[i-1] = y[i];
          y[i] = temp;
        }
      }
    }
  }

  for(int i=0; i<n; i++) {
    printf("%d %d\n", x[i], y[i]);
  }

  free(x);
  free(y);
}

> 시간초과 

 

2) swap 함수 사용하기 

#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do {type t = x; x = y; y = t;} while(0)

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

  int *x, *y; 
  x = calloc(n, sizeof(int));
  y = calloc(n, sizeof(int));

  for(int i=0; i<n; i++) {
    scanf("%d %d", &x[i], &y[i]);
  }

  for(int j=0; j<n; j++) {
    for(int i=1; i<n; i++) {
      if(x[i-1] > x[i]) {
        swap(int, x[i-1], x[i]);
        swap(int, y[i-1], y[i]);
      }   
    }
  }

  for(int i=1; i<n; i++) {
    if(x[i-1] == x[i]) {
      if(y[i-1] > y[i]) {
        swap(int, y[i-1], y[i]);
      }  
    }
  }

  for(int i=0; i<n; i++) {
    printf("%d %d\n", x[i], y[i]);
  }

  free(x);
  free(y);
}

 > 시간초과 실패.. 

코드 수는 줄어도 i, j번 반복해야 하는 건 똑같다. 

 

3) qsort 함수 사용 

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

int int_cmp(const int *a, const int *b) {
  if(*a < *b)
    return -1;
  else if(*a > *b)
    return 1;
  else
    return 0;
}

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

  int *x, *y; 
  x = calloc(n, sizeof(int));
  y = calloc(n, sizeof(int));

  for(int i=0; i<n; i++) {
    scanf("%d %d", &x[i], &y[i]);
  }

  qsort(x, n, sizeof(int), (int(*)(const void *, const void *)) int_cmp);
  qsort(y, n, sizeof(int), (int(*)(const void *, const void *)) int_cmp);

  for(int j=0; j<n; j++) {
    for(int i=1; i<n; i++) {
      if(x[i-1] == x[i]) {
        if(y[i-1] > y[i]) 
          swap(int, y[i-1], y[i]);
      } 
    }
  }

  for(int i=0; i<n; i++) {
    printf("%d %d\n", x[i], y[i]);
  }

  free(x);
  free(y);
}

> 시간초과 

헤더	#include <stdlib.h>
형식	void qsort(void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *));
해설	base : 정렬할 배열  nmemb : 요소의 개수  size : 배열 요소 크기 compar : 비교 함수 > compar에 지정한 비교 함수를 사용하여 정렬한다. compar에 전달할 비교 함수는 다음과 같은 기능을 할 수 있도록 직접 작성해야 한다.  1) 첫번째 인수가 두번째 인수보다 작은 경우에는 음수(-1)를, 같을 경우에는 0, 클 경우에는 양수를 반환한다.  2) 비교하는 두 요소가 같을 경우에는 순서를 다시 재배치하지 않는다. 같은 키 값을 가지고 있는 데이터가 2개 이상인 경우 오름차순으로 정렬되긴 하지만, 정렬 전후의 데이터가 같은 순서를 유지하지는 않는다. (안정된 배열이 아님)

x와 y를 qsort의 요소로 보내서 정렬하고 x의 두 요소 값이 같을 경우 y 값을 비교해서 오름차순 정렬하려고 했으나 실패..

 

4) 결국 검색.. (참고 : https://kyr-db.tistory.com/59)

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

typedef struct{
    int x, y;
} Point;

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

int main(){
    int N;
    scanf("%d", &N);
    Point p[N];
    for (int i = 0; i < N; i++)
        scanf("%d %d", &p[i].x, &p[i].y);
    qsort(p, N, sizeof(Point), compare);
    for (int i = 0; i < N; i++)
        printf("%d %d\n", p[i].x, p[i].y);
}

1. 구조체를 이용하여 x와 y 한꺼번에 처리하기
2. qsort를 사용해서 구조체 p 정렬하기 
3. 두번째 요소의 x가 더 크다면 -1 반환, 
   앞 요소의 x가 더 크다면 1 반환, 
   그것도 아니라면 y값 비교해서 뒤 요소의 y가 더 크다면 -1, 앞 요소의 y가 더 크다면 1을 반환한다. 

 

정리) 2개의 배열이 필요한 정렬에서는 구조체, qsort 함수 이용하기