no.18870 좌표 압축

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;


int main()
{

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int N;
	cin >> N;
	vector<int > v(N);

	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}

	vector<int> sorted = v;
	sort(sorted.begin(), sorted.end());
	sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());

	for (int i = 0; i < N; i++) {
		cout << lower_bound(sorted.begin(), sorted.end(), v[i]) - sorted.begin() << ' ';
	}

	return 0;
}

 

문제분석 

맨 처음에는 set을 받아서 풀면되는건가? 라는 생각을 했지만 

sort와 algorithm 헤더에 포함된 메소드들로 풀 수 있다는 사실을 파악했다. 

 

sort(sorted.begin(), sorted.end())

• 헤더: <algorithm>
• 동작: sort는 [first, last) 구간을 오름차순 정렬한다

sorted 벡터 전체 구간에 대한 정렬을 진행한다. 

정렬 후, 동일 원소들이 연속 위치하게 된다 

 

unique(sorted.begin(), sorted.end())

• 헤더: <algorithm>
• 동작: 연속된 중복 원소를 제거하고, 중복이 없는 상태를 만들기 위한 “새로운 끝” 이터레이터를 반환.
  • 실제로 컨테이너 크기를 줄이지 않고, “중복 아닌” 원소들을 앞에 모으고, 뒤쪽에 불필요한 원소가 남아있도록 정리만 함.
  • 반환 값으로는 중복이  제거된 유효구간 끝을 가르키는 이터레이터를 반환함 

따라서 unique한 값을 sorted.erase 메소드를 이용하여 물리적으로 제거해주어야함 

 

sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());

 

즉 이코드는 유니크 값을 이용하여 sorted 배열을 정리한 후, 반환 이터레이터, 즉 유효구간 끝에서 벡터 끝까지 지워주게됨

중복된 값들이 사라진다. 

 

lower_bound(sorted.begin(), sorted.end(), v[i])

• 헤더: <algorithm>
• 동작: 이진 탐색으로, [first, last) 구간에서 정렬된 상태를 가정하에, “v[i] 이상이 처음 나타나는 위치”(이터레이터)를 찾는다.

정렬 + 중복이 제거된 sorted에서 v[i] 인덱스가 몇번쨰 인덱스인지 찾기 위해 사용한다.

반환 값으로는 이터레이터가 오기 때문에, 인덱스를 얻기 위해서는 해당 이터레이터가 컨테이너의 시작 

즉 sorted.begin으로부터 몇번째 떨어져 있는지를 계산해야함

 

인덱스를 구하려면 꼭 -sorted.begin이 필요함!