[BOJ 2164] 백준 좌표 압축 풀이 - C++

사용언어 :  C++

 

 

 

 

문제풀이

* vector 이용!! (sort, erase, unique, lower_bound)

(1) 2개의 vector가 필요하다. original vector, check vector

original vector : 순서대로 좌표압축 값을 출력해야함

check vector : 좌표압축 값 계산할 때 사용 

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

 

(2) check vector 변형해주기

중복되지 않는, 오름차순으로 정렬해주기. 

=> 오름차순 정렬 후 중복된 값은 뒤로 보내준다. 중복된 값들은 다 지워준다. (중복 시작 된 곳부터 끝까지)

sort(check.begin(), check.end());
check.erase(unique(check.begin(), check.end()), check.end());

sort(v.begin(),v.end()); //오름차순 정렬

unique(v.begin(),v.end()); // 중복된 값은 뒤로 보내준다 

ex) 1 3 4 2 2 5 3 1 => 1 3 4 2 5 2 3 1

erase(v.begin(),v.end()); //v.begin()~v.end()사이 원소값 지워주기

 

 

(3) check vector를 이용해 original vector 좌표압축 값 구하기

	for (int i = 0; i < n; i++) {
		cout<< lower_bound(check.begin(), check.end(), v[i]) - check.begin()<<" ";
	}

lower_bound(arr,arr+n,key) // arr~arr+n 사이에 key의 위치 리턴해주기 

// 리턴 타입이 iterator이기 때문에 몇 번째 인자인지 알기 위해선 v.begin()을 빼준다. 

 

 

 

전체코드

 

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


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

	sort(check.begin(), check.end());
	check.erase(unique(check.begin(), check.end()), check.end());

	for (int i = 0; i < n; i++) {
		cout<< lower_bound(check.begin(), check.end(), v[i]) - check.begin()<<" ";
	}
}

 

 

 

총평

좀 어려웠다... 벡터 기능을 잘 활용해야 하는 문제!

---

문제 출처

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

18870번: 좌표 압축