백준 알고리즘 18870번: 좌표 압축 [C++]

문제 출처: www.acmicpc.net/problem/18870

18870번: 좌표 압축

1. 코드

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

using namespace std;

int main(void)
{
	int n;
	cin >> n;	//원소의 갯수 입력

	vector <int> v(n);			//원소의 갯수만큼 백터 할당 
	for (int i = 0; i < n; i++)
		cin >> v[i];			//원소 값 입력

	vector <int> r(v);			//기존의 백터 v 복사
	sort(r.begin(), r.end());	//오름차순으로 정렬
	r.erase(unique(r.begin(), r.end()), r.end());			//중복 제거

	for (int i = 0; i < n; i++)
	{
		auto it = lower_bound(r.begin(), r.end(), v[i]);	//입력순으로 입력값 위치 탐색
		cout << it - r.begin() << " ";
	}
}

(실행)

2. 풀이

int n;
cin >> n;	//원소의 갯수 입력

먼저 입력할 원소의 갯수를 입력한다.

vector <int> v(n);			//원소의 갯수만큼 백터 할당 
for (int i = 0; i < n; i++)
    cin >> v[i];			//원소 값 입력

입력한 원소의 갯수와 동일한 크기의 vector를 생성하고 각 원소들을 반복문을 이용하여 입력한다. 그리고 해당 값들을 이용하여 탐색을 해야하는데 v 백터는 탐색을 하기 위한 key값으로 다른 백터를 생성해준다.

vector <int> r(v);                               //기존의 백터 v 복사
sort(r.begin(), r.end());                        //오름차순으로 정렬
r.erase(unique(r.begin(), r.end()), r.end());    //중복 제거

r 백터 생성하는데 백터 v를 복사한다. 그리고 sort 함수를 이용하여 오름차순으로 r 백터의 원소들을 정렬해주고, 입력된 원소들 중 중복된 값이 있을 수 있으니 그것을 unique() 함수와 erase() 함수를 통해 제거를 해준다.

for (int i = 0; i < n; i++)
{
    auto it = lower_bound(r.begin(), r.end(), v[i]);	//입력순으로 입력값 위치 탐색
    cout << it - r.begin() << " ";
}

마지막으로 반복문을 이용하여 입력한 모든 값들의 좌표를 찾아줘야 하는데 find() 함수를 이용해서 찾을 수는 있지만 시간 초과가 발생하는데 그 이유는 find() 함수는 시간복잡도가 O(n)인데 반복문을 이용하여 다시 찾으니 사실상 시간 복잡도는 O(n^2)이 된다.

그래서 시간 복잡도가 O(log(end - begin))이고, 이진탐색 기반인 lower_bound() 함수를 이용하여 위치를 찾아내어서 해당 값을 타입 추론인 auto를 활용하여 저장하고 출력을 해야하는데 r.begin() 빼면 출력이 가능하다.

3. 느낀 점

C++에 대해 공부를 하며 알고리즘 문제를 풀어보니 확실히 C++에 대한 기초적인 지식이 많이 부족하다는 것을 많이 느꼈다. sort() 함수에 대해서는 알았지만 unique() 함수, erase() 함수, lower_bound 함수 그리고 타입 추론 auto에 대해 하나도 몰랐기에 오랜 삽질 끝에 결국 검색을 해서 답을 알아냈는데 부족한 점을 많이 느꼈다.