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

1. 문제

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

18870번: 좌표 압축

 

 

2. 풀이 과정

핵심 로직 : 정렬, 중복제거, 이분탐색

위 로직들은 C++ 내장 라이브러리, 함수를 사용하면 좀 더 쉽게 표현 가능하지만 아직 수련중이라 직접 구현해보았다.

 

아이디어

1. 입력 받은 좌표를 long long int 크기의 배열1 에 저장해 놓는다.

2. 배열1과 같은 배열2를 만들고 정렬, 중복 제거 수행

3. 배열2에서 배열 1의 값을 이분 탐색으로 찾고 그때 배열 2의 인덱스를 출력한다.

이때 인덱스가 해당 수보다 작은 수들의 갯수를 나타낸다.

Num(배열)	-10	-9	2	4
Index	0	1	2	3

특정 좌표 값을 찾고 그때의 인덱스가 특정 좌표 값 앞에 있는 좌표들의 갯수임을 알 수 있다. 

 

📁 전체 코드는 아래에 있습니다.

1. 이분탐색 코드

int findindex(long long int* arr, int n, long long int target) //이분탐색
{
	int left = 0;
	int right = n-1;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (arr[mid] < target)
			left = mid + 1;
		else if (arr[mid] > target)
			right = mid - 1;
		else
			return mid;
	}		
	return 0;
}

 

2. 정렬 및 중복 제거 코드

sort(sortNum, sortNum + n); //정렬 수행

result[0] = sortNum[0]; //중복 제거 수행
int resultSize = 1;  
for (int i = 0; i < n - 1; i++)
{
	if (sortNum[i] != sortNum[i + 1])
	{
		sortNum[resultSize++;] = sortNum[i + 1];
	}
}

 

 

3. C++ 정답코드

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

int findindex(long long int* arr, int n, long long int target) //이분탐색
{
	int left = 0;
	int right = n-1;
	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (arr[mid] < target)
			left = mid + 1;
		else if (arr[mid] > target)
			right = mid - 1;
		else
			return mid;
	}		
	return 0;
}

int main()
{
	int n;
	cin >> n;
	long long int num[1000000];
	long long int sortNum[1000000];
	
	for (int i = 0; i < n; i++) //좌표 값 입력받음
	{
		cin >> num[i];
		sortNum[i] = num[i];
	}

	sort(sortNum, sortNum + n); //정렬 수행

	int resultSize = 1;  
	for (int i = 0; i < n - 1; i++) //중복 제거
	{
		if (sortNum[i] != sortNum[i + 1])
			sortNum[resultSize++] = sortNum[i + 1];
	}

	for (int i = 0; i < n; i++)  //이분탐색 수행 후 인덱스 반환
		cout << findindex(sortNum, resultSize, num[i]) << " ";

	return 0;
}