백준 11650번

좌표 정렬하기 성공

시간 제한 메모리 제한

1 초 256 MB

문제

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

입력

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

출력

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

해설

이 문제 같은 경우 좌표를 받고 x가 작은순에서 커지는순으로 x값이 같으면 y의 크기순으로 오름차순으로 정렬하는 문제이다 그래서 순차정렬을 이용한 소스코드를 작성했다

#define _CRT_SECURE_NO_WARNINGS    
#include <stdio.h>
#include <string.h>

int main() {
	int a;
	scanf("%d", &a);
	int b[a], c[a], temp[2];
	for (int i = 0; i < a; i++)
	{
		scanf("%d %d", &b[i], &c[i]);
	}
	for (int i = 0; i < a; i++)
		for (int j = 0; j < a - 1; j++)
			if (b[j] > b[j + 1]) {

				temp[0] = b[j];
				b[j] = b[j + 1];
				b[j + 1] = temp[0];


				temp[1] = c[j];
				c[j] = c[j + 1];
				c[j + 1] = temp[1];
			}
			else if (b[j] == b[j + 1])
			{
				if (c[j] > c[j + 1])
				{
					temp[0] = b[j];
					b[j] = b[j + 1];
					b[j + 1] = temp[0];


					temp[1] = c[j];
					c[j] = c[j + 1];
					c[j + 1] = temp[1];
				}
			}
	for (int i = 0; i < a; i++)
	{
		printf("%d %d\n", b[i], c[i]);
	}
}

이렇게 정렬했더니 시간초과가 나온다 10만개의 테스트케이스를 순차정렬에 사용하기에는 시간 복잡도가 O(N^2)가 된다 그러므로 qsort를 이용해서 풀어야한다 하지만 qsort는 배열에 변수를 하나만 넣을 수 있다 그래서 방법을 찾던중 coord구조체를 이용하여 푸는 방법을 찾았다 coord 구조체에 x와 y값을 받고 배열로 만들면 qsort에 넣을 수있다 그럼 풀어보자

#define _CRT_SECURE_NO_WARNINGS    
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct _COORD {
	int x;
	int y;
} COORD;

int compare(const void* a, const void* b) {
	COORD num1 = *(COORD*)a;
	COORD num2 = *(COORD*)b;
	if (num1.x > num2.x)
	{
		return 1;
	}
	else if (num1.x == num2.x)
	{
		if (num1.y > num2.y)
		{
			return 1;
		}
		else {
			return -1;
		}
	}
	return -1;
}

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

Written on September 22, 2022