[BaekJoon/C] No.18870 : 좌표 압축

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

No.18870 문제

 

문제해석

 

좌표 압축은 입력으로 주어진 좌표 값들을 오름차순으로 정렬한 후, 중복되는 값을 하나의 값으로 치환하고, 고유한 값을 순서대로 0부터 작은 숫자로 변환하는 것입니다.

 

1) 입력받은 좌표값 오름차순으로 정렬합니다 (기존 위치는 loc에 그대로 저장)

2) 가장 작은 수부터 숫자 0 배정 후 값이 올라갈수록 +1 해줍니다

3) 정렬된 값을 다시 기존 위치로 되돌려 줍니다

4) 기존 위치에 오름차순으로 배정된 압축값을 출력합니다

 

 

입력받은 값과 순서, 압축된 좌표값을 묶어 구조체를 만들어 줍니다 : struct

C에서 제공하는 정렬함수를 사용하여 입력받은 값을 비교하여 오름차순으로 정렬한 뒤 압축된 값을 배정하는 함수를 작성해줍니다 : 정렬함수 - qsort / qsort에서 사용할 비교함수 - compare

 

flag라는 변수를 이용해 compare 함수에서 x로 정렬할 지 loc기준으로 정렬할 지 판단하도록 해줍니다

 

좌표의 개수는 정해져 있지 않기 때문에 동적메모리를 할당하여 개수에  맞춰 적절한 크기의 메모리를 확보합니다
: calloc (malloc과는 다르게 할당된 메모리의 모든 바이트를 0으로 초기화해줍니다)

 

 

소스코드 & 문제풀이

 

#include<stdio.h>
#include<stdlib.h> // qsort 함수를 제공합니다

// 구조체(입력받은 값, 입력받은 순서, 압축된 좌표값)를 사용해 연관된 변수를 묶어줍니다
typedef struct _Coord {
	int x; // 입력받은 값
	int loc; // 입력받은 순서
	int compress; // 압축된 좌표값
} Coord;

int flag;	// flag 변수 선언하여 flag 값에 따라 결과값이 달라지도록 합니다 

// qsort에서 사용할 비교함수를 선언합니다
int compare(const void* a, const void* b) {
	Coord A = *(Coord*)a;
	Coord B = *(Coord*)b;
	
    // flag가 0이면 x를 기준으로 정렬합니다
	if (!flag) {
		if (A.x > B.x)
			return 1; 
		else if (A.x < B.x)
			return -1; 
		else
			return 0;
	}
    // flag가 1이면 loc를 기준으로 정렬합니다
	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)); // 동적메모리 할당
	
    // 입력받은 좌표 개수만큼 반복하며 순서를 기억하기 위해 loc 인덱스에 좌표값 입력받고 저장합니다
    for (i = 0; i < N; i++) {
		scanf("%d", &coord[i].x);
		coord[i].loc = i;
	}
    
	// 값(x)을 기준으로 정렬합니다
	qsort(coord, N, sizeof(Coord), compare);

// 정렬된 좌표를 비교하면서 중복된는 좌표는 같은 압축 값을 부여하고
// 중복되지 않는 좌표는  이전 값보다 1큰 값을 부여하여 압축합니다
	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;
}

 

 

예제 입출력 결과

 

예제1

 

 

 

예제2