[백준/C & C++] 18870 좌표 압축

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

18870번: 좌표 압축

C

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

int cmp(const void* a, const void* b)
{
	int num1 = *(int*)a;
	int num2 = *(int*)b;

	if (num1 > num2) return 1;
	else if (num1 < num2) return -1;
	else return 0;
}

int binsearch(int find, int arr[], int low, int high)
{
	while (low <= high)
	{
		int mid = (low + high) / 2;
		if (find == arr[mid]) return mid;
		else if (find > arr[mid]) low = mid + 1;
		else high = mid - 1;
	}
	return -1;
}

int main()
{
	int n, k=0;
	scanf("%d", &n);
	int* arr = (int*)malloc(sizeof(int) * n);
	int* check = (int*)malloc(sizeof(int) * n);
	int* result = (int*)malloc(sizeof(int) * n);

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
		check[i] = arr[i];
	}

	qsort(check, n, sizeof(int), cmp);
	result[0] = check[0];
	for (int i = 1; i < n; i++) if (check[i - 1] != check[i]) result[++k] = check[i];
	for (int i = 0; i < n; i++) printf("%d ", binsearch(arr[i], result, 0, k));

	free(arr);
	free(check);
	free(result);
	return 0;
}

C++

#include <iostream>
#include <cstdlib>
#include <algorithm>
using namespace std;

int binsearch(int find, int arr[], int low, int high)
{
	while (low <= high)
	{
		int mid = (low + high) / 2;
		if (find == arr[mid]) return mid;
		else if (find > arr[mid]) low = mid + 1;
		else high = mid - 1;
	}
    return -1;
}

int main()
{
	int n, k=0;
	cin >> n;
	int* arr = new int[n];
	int* check = new int[n];
	int* result = new int[n];

	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
		check[i] = arr[i];
	}

	sort(check, check + n);

	result[0] = check[0];
	for (int i = 1; i < n; i++) if (check[i - 1] != check[i])  result[++k] = check[i];
	for (int i = 0; i < n; i++) cout << binsearch(arr[i], result, 0, k) << " ";

	delete[]check;
	delete[]arr;
	delete[]result;
	return 0;
}

코드 설명

좌표 압축의 결과는 본인보다 작은 좌표의 개수다.

나의 경우 입력을 저장하는 배열 arr, arr를 오름차순으로 정렬한 배열 check, 결과를 저장하는 result배열을 동적으로 할당한 후 문제를 다 푼 후에 해제했다. arr배열을 바로 오름차순으로 정렬하지 않은 이유는 결과를 출력할 때는 입력된 순서대로 출력이 되어야하기 때문이다. 구조체를 사용한 풀이도 가능할 것 같다.

 

arr배열에 숫자들을 입력받고, 바로 check배열에 입력된 숫자를 저장한다. 이후 check배열을 정렬한다. C의 경우 qsort, C++의 경우 algorithm 헤더에 내장된 sort함수를 사용했다.

 

입력된 숫자 중 가장 작은 값을 result[0]에 저장한다. 이후 1부터 n-1까지 반복문을 돌면서 check배열의 연속된 두 값이 같지 않을 경우  더 큰 값을 result[++k]에 저장한다. (입력으로 들어오는 수에 중복된 값이 있을 수 있으므로 중복된 값을 제거한 배열 result를 생성한다.)

 

다시 반복문을 돌면서 이진탐색으로 중복이 존재하지 않는 result 배열에서  arr[i]의 값의 위치를 찾아 출력한다.

 

느낀 점

c++로 코드를 작성할 때 binsearch함수 내 while문 조건을 실수해서 한 번 틀렸다.