[백준 / C언어] 18870번: 좌표 압축 (구조체 이용)

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

18870번: 좌표 압축

 

난이도: solved.ac 실버 2

 

알고리즘 분류

---

정렬, 값 / 좌표 압축

 

접근 방법 및 구현

---

Coord라고 하는 구조체(struct)를 만들어 배열로 만들어주었다.

이 구조체의 원소는 x, loc, compress가 있는데, 각각 입력받은 숫자, 입력받은 순서, 압축된 숫자를 의미한다.

좌표 압축을 하기 위한 순서는 다음과 같다.

 

1. 값(x)을 오름차순으로 정렬 (이때 기존의 나열 순서는 loc에 그대로 저장되어 있음)

2. 가장 작은 수부터 시작해 0부터 숫자를 배정 (배정된 숫자는 compress에 저장)      * 압축 단계

3. 오름차순으로 정렬된 숫자들을 원래의 순서대로 다시 되돌림

4. 첫 번째 숫자부터 시작해 압축된 숫자(compress)를 출력

 

정렬은 c언어 내장 함수인 qsort를 이용했고, compare함수에서는 flag라는 변수를 이용해 flag가 0이면 x로 정렬하고, flag가 1이면 loc로 정렬하도록 했다.

 

코드

---

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

typedef struct _Coord {
	int x;		// 입력 받은 값
	int loc;	// 입력 받은 순서(위치)
	int compress;	// 압축된 좌표 값
} Coord;

int flag;	// flag가 1이면 위치를 

int compare(const void* a, const void* b) {
	Coord A = *(Coord*)a;
	Coord B = *(Coord*)b;
	// 값 정렬
	if (!flag) {
		if (A.x > B.x)
			return 1;
		else if (A.x < B.x)
			return -1;
		else
			return 0;
	}
	else {	// 위치 번호 정렬
		if (A.loc > B.loc)
			return 1;
		else if (A.loc < B.loc)
			return -1;
		else
			return 0;
	}
}

int main() {
	int N, i;
	scanf("%d", &N);
	Coord* coord = (Coord*)calloc(N, sizeof(Coord));
	for (i = 0; i < N; i++) {
		scanf("%d", &coord[i].x);
		coord[i].loc = i;
	}
	// 값(x)을 기준으로 정렬
	qsort(coord, N, sizeof(Coord), compare);

	// 숫자 압축
	for (i = 1; i < N; i++) {
		if (coord[i].x == coord[i - 1].x)
			coord[i].compress = coord[i - 1].compress;
		else
			coord[i].compress = coord[i - 1].compress + 1;
	}
	flag = 1;
	// 기존 순서로 돌리기 위해 위치를 기준으로 정렬
	qsort(coord, N, sizeof(Coord), compare);

	for (i = 0; i < N; i++)
		printf("%d ", coord[i].compress);
	return 0;
}