[1주차] 백준 11651: 좌표 정렬하기2_C언어

백준 11651: 좌표 정렬하기2

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

11651번: 좌표 정렬하기 2

---

-> 점의 개수(N)을 입력받고, 각 x와 y 좌표를 입력받는다. 

-> y의 오름차순, y가 같다면 x의 오름차순으로 점들을 출력한다. 

---

#1) 첫 번째 시도 -> 시간 초과

#include <stdio.h>

int main(void) {

	int N;

	int x[100000];
	int y[100000];


	scanf("%d", &N);

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

	for (int j = 0; j < N; j++) {
		for (int w = j + 1; w < N; w++) {
			if (y[j] > y[w]) {
				int t;
				t = y[j];
				y[j] = y[w];
				y[w] = t;

				int p;
				p = x[j];
				x[j] = x[w];
				x[w] = p;

			}
			else if (y[j] == y[w]) {
				if (x[j] > x[w]) {
					int q;
					q = x[j];
					x[j] = x[w];
					x[w] = q;
				}
			}
		}
		printf("%d %d\n", x[j], y[j]);
	}

	return 0;
}

- x와 y를 각 배열로 입력받고, 순서대로 비교해보며 값을 바꾸면 된다고 생각했다.

* 시간 초과같은 경우는 어떻게 예상하고 사전에 방지해야하는지 잘 모르겠다.. 솔직히 시간같은 건 내가 어떻게 제어해야 하는지도 아직 잘 모르겠다.. 휴

---

#2) 두 번째 시도 

* 코드참고 : https://sedangdang.tistory.com/16

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

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

int compare(const void* first, const void* second)
{
	coord* a = (coord*)first;
	coord* b = (coord*)second;

	if (a->y < b->y)
		return -1;
	else if (a->y > b->y)
		return 1;
	else
	{
		if (a->x < b->x)
			return -1;
		else
			return 1;
	}
}

int main()
{
	int i, N;
	coord* list;   

	scanf("%d", &N);
	list = (coord*)malloc(N * sizeof(coord));

	for (i = 0; i < N; i++)
	{
		scanf(" %d %d", &list[i].x, &list[i].y);
	}
	
	qsort(list, N, sizeof(list[0]), compare);

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

	free(list);
	return 0;
}

- 구조체를 선언하고 퀵소트 함수를 통해서 정렬해준다.

* 아무리 생각해도 계속 머리가 꼬여서 구글링했다. 구조체를 이용해서 푸는 방법이 많이 나와있는데 이해가 안돼서 구조체 개념 다시 정리해보았다. qsort함수를 이용해서 푸는 방법이 가장 이해가 잘되어서 코드를 참고해 분석했다. 나중에 다시 풀어봐야겠다.

* [구조체 개념 정리]: https://mnzy.tistory.com/4

---

-> qsort/compare함수 정리

https://en.wikipedia.org/wiki/Quicksort

- Quick sort : pivot을 정하고 pivot보다 작은 값들을 pivot의 왼쪽 pivot보다 큰 값들은 pivot의 오른쪽으로 위치시키고 pivot의 왼쪽 값들과 오른쪽값들도 각 각 따로 정렬해준다.

- (c언어) stdlib.h에서 qsort함수를 제공해준다.  //즉, 호출만 해주면 됨

- ex.

 -> qsort(list, N, sizeof(list[0]), compare);    

 -> list: 정렬하고자 하는 배열의 포인터

 -> N: 배열의 원소 개수

 -> sizeof(list[0]): 배열의 원소 하나의 크기

 -> compare: 비교를 수행할 함수 

 

- comapare 함수

-> compare 함수의 리턴값은 기본적으로 오름차순

-> 리턴 값이 0보다 작을 경우 first < second

-> 리턴 값이 0보다 클 경우 first > second

-> 리턴값이 0이면 두 값이 같음

 

* 참고

https://twpower.github.io/56-qsort-in-c

https://m.blog.naver.com/xxxstarxxx/221388492777

---

처음에 당연히 정답일 줄 알고 있었는데 시간초과.. 이후에 혼자 해결해보려다가 시간이 꽤 오래 걸렸다.

혼자만으로 해결할 수 없을 것 같아서 구글링을 했는데, 구조체를 사용해야 하는 것 같아서 당황했다.

구조체는 잘 안쓰던 개념이라 많이 까먹었다. 이번 기회에 복습해서 차라리 다행인 것 같다.