문제
2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다.
출력
첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다.
정렬 문제이다. 값 2개를 한 번에 받아올 방법이 도저히 떠오르지 않아 처음엔 동적 배열로 코드를 짜려고 했다. 그러나, 생각해보니 구조체라는 좋은 자료형이 존재했기 때문에, 구조체에 대해 다시 복습도 할 겸 문제를 적는게 좋을 것 같았다.
구조체란
C언어에서 사용할 수 있는, 구조화된 데이터를 처리할 때 사용하는 자료형이다. 여러 변수를 하나의 세트로 묶어 사용한다고 보면 될 것이다.
우리들의 지식 창고 나무위키를 참고하여, 구조체의 예를 보도록 하겠다.
struct Position //Position형 구조체 선언
{
int Xposition; //정수형 Xposition 선언
int Yposition; //정수형 Yposition 선언
};위치를 지정할 때, 변수 X와 Y를 따로 두는 것이 아닌, Position이라는 구조체 안에 X와 Y 변수를 한번에 선언하여 하나의 변수처럼 이용하는 것이다. C++이나 Java, C#에서 사용하는 클래스와 비슷하고, 심지어 상속까지도 구현되어있다고 한다. C언어로 문제를 풀기는 하지만, Java도 해보고 Unity Engine에서 사용하는 C#도 해본 나로서는 뭔가 클래스 쪽이 더 익숙한 것 같았다.
이렇게 설정한 구조체를 실제로 사용하기 위해서는, 이런 식으로 선언해준다.
struct Position position1;
struct Position position2;매번 struct를 적어주기 귀찮다면, 특정 위치에 별명과 비슷하게 사용할 수 있는 단어를 집어넣으면 그렇게 사용할 수 있다.
struct Position //Position형 구조체 선언
{
int Xposition; //정수형 Xposition 선언
int Yposition; //정수형 Yposition 선언
}position; // struct Position -> position으로 사용할 수 있음
position position1;
position position2;구조체 변수 내의 특정 변수에 접근하기 위해서는, 밑의 방식을 따르게 된다.
position1.x = 10;
position1.y = 20;
position2.x = 30;
position2.y = 40;구조체의 대한 설명은 여기까지이고, 코드를 잠시 확인해보겠다.
2차원 동적 배열을 사용하는 대신, 구조체 배열을 이용해서 x, y 좌표를 표현할 수 있다.
typedef struct coord
{
int x;
int y;
}coord;필자는 이런 식으로 구조체를 작성했고, 나머지는 정렬하는 것 뿐이었다.
사실 구조체를 떠올리는 것보다, 정렬 알고리즘을 어떻게 작성해야 하는 것인가에 대해 고민을 꽤 많이 했던 것 같다. 지금 생각해보면 단순히 x만 비교하는 것이 아닌, x가 같을 경우 y를 비교해야하는 것이 꽤 헷갈렸던 것 같다.
결론부터 말하자면, 이미 내장되어있는 qsort 함수를 그대로 사용하는 대신, 비교 함수를 조금 수정하는 간단한 방법으로 문제를 풀 수 있었다.
qsort 함수의 원형은 다음과 같다.
void qsort(
void *base,
size_t number,
size_t width,
int (__cdecl *compare )(const void *, const void *)
);첫 줄부터
정렬해야하는 자료들
자료의 양
자료 1개의 크기
정렬할 때 사용할 비교 함수
를 의미한다.
여기서 눈여겨 볼 것은 바로 비교 함수이다.
이전에 qsort를 사용하여 백준에 제출할때는, 구글 검색을 통해 가지고 온 compare 함수를 그대로 사용했지만, 이 참에 제대로 한번 뜯어보겠다.
int compare(const void* a, const void* b)
{
int num1 = *(int*)a;
int num2 = *(int*)b;
if (num1 < num2)
return -1;
if (num1 > num2)
return 1;
return 0;
}우선 qsort 함수에 있는 비교 함수를 보면, 무조건 const void* 형 변수를 2개 가지는 함수여야 한다.
const void* : void형 상수를 가리키는 포인터
qsort 함수를 통해 compare 함수가 포인터를 전달 받았을 때, 포인터가 가리키는 값 = 상수
-> compare 함수 안에서는 값을 임의로 바꿀 수는 없다.
a와 b에 원하는 값을 가지고 온 후, 이 함수에서는 int 형이기 때문에 int * 형으로 변환한 후 역참조한다. 이렇게 함으로서 num1과 num2에 원하는 값을 받아올 수 있다.
오름차수 정렬 조건은 다음과 같다:
a < b -> -1을 반환
a > b -> 1을 반환
a == b -> 0을 반환
내림차수는 위 조건에서 등호 방향만 바꾸어주면 될 것이다.
위 조건을 확인했을 때, 위 compare 함수는 오름차순 정렬을 위한 compare 함수라는 것을 알 수 있다.
그럼 이걸로 어떻게 구조체를 정렬할 수 있을까? 답은 생각 외로 간단했다. 바로 위 compare 함수에 있는 int형을 아까 설정한 구조체형으로 바꿔주기만 하면 된다.
int compare(const void* a, const void* b)
{
coord num1 = *(coord*)a;
coord num2 = *(coord*)b;
if (num1.x < num2.x) // 구조체 자체와의 비교는 불가능하니,
//구조체 변수 내부의 변수끼리 크기를 비교한다.
return -1;
if (num1.x > num2.x)
return 1;
return 0;
}이렇게 되면, 구조체의 x좌표끼리 비교하여 오름차순으로 정렬하는 함수가 되었다. 그럼, 비교하는 좌표의 x값이 같다면, return 0을 해주는 것이 아닌 각 좌표의 y 값을 비교하여, 순서를 따로 부여해주는 코드가 필요할 것이다.
int compare(const void* a, const void* b)
{
coord num1 = *(coord*)a;
coord num2 = *(coord*)b;
if (num1.x < num2.x)
return -1;
if (num1.x > num2.x)
return 1;
else
if (num1.y < num2.y)
return -1;
if (num1.y > num2.y)
return 1;
}각 좌표의 x 값이 같다면, 각 좌표의 y를 비교해 오름차순으로 정렬하게 만드는 compare 함수이다.
필자는 유니티로 게임 개발을 하다 보니, 클래스에 너무 익숙해져서 원래 사용하던 구조체를 조금 까먹었었다. 그래서, 이번 문제를 풀면서 구조체를 오랜만에 복기할 수 있었고, c언어 내장함수 qsort에 대해 조금 더 자세히 알 수 있었다.
