[백준] 18870 - 좌표 압축

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

18870번: 좌표 압축

 

 

알고리즘 방식

간단히 예제를 통해 생각하면,

[2, 4, -10, 4, -9]

내림차순 정렬과 중복 제거 후

전체 크기에서 현재 인덱스의 값을 빼주면 해당 인덱스의 좌표 압축 결과였다.

중복 제거는 <algorithm> 헤더의 unique 함수를 통해 O(N)으로 구현할 수 있다. 

(unique 함수는 중복 제거된 벡터의 마지막 값을 iterator로 반환한다.)

 

따라서, 원본 배열(v)과 위의 과정을 진행할 배열(sortedV)을 각각 만들고

v에 저장된 값을 sortedV에서 이분탐색을 통해 찾고

sortedV에서 찾은 인덱스를 통해 좌표 압축의 결과를 차례대로 출력한다.

 

 

 

소스코드

/*
Date :
Time : 01:30 ~
Comment :

*/

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;


int N;
vector<int> v;
vector<int> sortedV;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;
	int order = 0;
	int input;
	for (int i = 0; i < N; i++) {
		cin >> input;
		v.push_back(input);
		sortedV.push_back(input);
	}

	sort(sortedV.begin(), sortedV.end(), greater<>());

	////중복제거 (O(N^2)
	//vector<int>::iterator it = sortedV.begin();
	//while (it != sortedV.end()) {
	//	if (next(it, 1) != sortedV.end() && *it == *next(it, 1)) {
	//		it = sortedV.erase(it);
	//		continue;
	//	}
	//	it++;
	//}
	//중복제거2 (O(N))
	sortedV.resize(unique(sortedV.begin(), sortedV.end()) - sortedV.begin());

	for (int i = 0; i < N; i++) {
		int target = v[i];
		int st = 0, en = sortedV.size() - 1;
		int mid;
		//cout << "target : " << target << '\n';
		while (st <= en) {
			mid = (st + en) / 2;
			if (sortedV[mid] < target)
				en = mid - 1;
			else if (sortedV[mid] > target)
				st = mid + 1;
			else {
				break;
			}
		}
		cout << sortedV.size() - (mid + 1) << ' ';
	}
}