BOJ-18870 | 좌표 압축 c++

✏️ 18870-좌표압축
🌊 GitHub @xaesu, Study-Algorithm

접근

✔️ 중복 값 제거 + 시간초과

벡터에 좌표 입력 후 중복 값을 제거하여 벡터를 복사하고,
복사한 벡터에서 입력 벡터 값이 해당하는 인덱스 값 반환
-> 복사한 벡터의 인덱스 값이 해당 값보다 작은 좌표의 개수

→ sort 함수 : 벡터 값 정렬 1,2,3,2 -> 1,2,2,3
→ unique 함수 : 중복되지 않은 값을 원소 앞으로 옮김 1,2,2,3 -> 1,2,3,x
→ erase : 지정 범위 원소 제거

→ vec.begin() : 벡터 vec의 첫번째 원소를 가리키는 반복자 반환
→ vec.end() : 벡터 vec의 마지막 원소 바로 다음을 가리키는 반복자
    유효 데이터 범위를 벗어난 가상의 위치를 가리킴

1. find 함수 사용
   → find : 지정 범위에서 지정 값 찾기

	int n;
	cin >> n;

	vector <int> coordinate(n);
	vector <int> copy(n);

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

	// 입력 값 복사
	copy = coordinate;

	// 중복값 제거 (비교 대상 확인)
	sort(copy.begin(), copy.end());
	copy.erase(unique(copy.begin(), copy.end()), copy.end());

	for (int i = 0; i < n; i++) {
		cout << find(copy.begin(), copy.end(), coordinate[i]) - copy.begin() << ' ';

    -> 선형탐색 방식 : 순차 검증 O(n) 의 시간 복잡도

2. lower_bound 함수 사용
   -> lower_bound : 정렬된 범위에서 특정 값보다 크거나 같은 첫 번째 원소의 반복자를 반환
   이분 탐색 방식으로, O(log N) 의 시간 복잡도를 가짐

풀이

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n;
	cin >> n;

	vector <int> coordinate(n);
	vector <int> copy(n);

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

	// 입력 값 복사
	copy = coordinate;

	// 중복값 제거 (비교 대상 확인)
	sort(copy.begin(), copy.end());
	copy.erase(unique(copy.begin(), copy.end()), copy.end());

	for (int i = 0; i < n; i++) {
        // lower_bound를 사용하여 이분 탐색
        cout << lower_bound(copy.begin(), copy.end(), coordinate[i]) - copy.begin() << ' ';
    }
}