정렬 - 18870번

1월 6일(금) - 정렬(18870번)

18870번: 좌표 압축

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

1. 첫 풀이에서는 pre_compress와 post_compress를 모두 구조체 변수로 선언했었고, 마지막 post_compress 를 print 하는 과정에서 자료형 오류가 발생했다.

-> %d를 print 해야하므로 post_compress의 자료형을 int로 변경하게되었다.

 

2. 첫 풀이에서는 compress 하는 과정을 따로 함수로 빼서 풀이를 진행하려했지만, 차라리 pre_compress 를 qsort 를 이용해서 오름차순으로 정리하는 것이 더 간단할 것 같아서 변경했다.

하지만 qsort 를 해서 오름차순으로 정렬을 해놓은 상황에서, 바로 이어서 위치해있는  pre_compress[i].number 중에서 중복되는 값이 있는지를 비교해보는 과정을 스스로 생각해내지 못했다.

-> min 변수의 최초값을 INT_MIN 으로 설정하고, 그 이후에는 직전의 pre_compress[i].number로 바꾼다는 생각을 하지 못했었다.

(참고 풀이 -> https://juintination.tistory.com/10)

 

3. min 을 INT_MIN 으로 설정했지만 정작 <limits.h>를 안넣고 돌리다가 컴파일에러가 발생했었다.

-> 풀이에서 오류가 발견된 경우, .h 파일 목록도 다시 한 번 확인해보도록 해야겠다.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

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

typedef struct coordinate{
	int index;
	int number;
}coordinate;

int compare(const void* a, const void* b)
{
	coordinate x = *(coordinate*)a;
	coordinate y = *(coordinate*)b;

	if (x.number > y.number)
	{
		return 1;
	}
	else if (x.number < y.number)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}

int main(void)
{
	int n;
	int count = -1;
	int min = INT_MIN;
	scanf("%d", &n);

	coordinate* pre_compress = (coordinate*)malloc(sizeof(coordinate) * n);
	int* post_compress = (int*)malloc(sizeof(int) * n);

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &pre_compress[i].number);
		pre_compress[i].index = i;

	}

	qsort(pre_compress, n, sizeof(coordinate), compare);

	for (int i = 0; i < n; i++)
	{
		if (pre_compress[i].number != min)
		{
			min = pre_compress[i].number;
			count++;
		}
		post_compress[pre_compress[i].index] = count;
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d ", post_compress[i]);
	}

	return 0;
}