[백준] 18870 좌표압축

 

 

 

계속 이진탐색을 활용한 정렬문제를 풀다보니 저절로 이진탐색이 떠올랐다..

해당 원소가 나머지 원소들과 비교했을 때 몇번째로 크냐?? 를 묻는 문제이므로,

vector를 정렬한 후에 저장된 원소를 하나씩 꺼내면서 이진탐색을 진행한다. 

 

단, v에서 중복원소를 지워야해서 좀 까다로웠다. 

처음 set을 사용했다가 std::set은 배열과같이 indexing이 안되므로 복잡해질거같아서 vector의 erase함수를 이용하기로 했다.

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

먼저 unique(v.begin(),v.end())는 가령 [3,3,4,1,5,5]배열이 있을 때 [3,4,1,5,5,5]로 만들어준다. 

즉, unique 함수를 적용하면 위와 같이 중복된 원소를 제거하며 앞에서부터 원소들을 채워나간다.

뒤쪽에 남은 자리는 기존의 vector원소로 채워진다.

 

여기서 erase(~~~,end())로 덮어주게 되면 ~~~자리에 있는 unique()함수가 위 예시배열에서

변하지 않는 부분(5,5)의 첫 위치를 리턴하기 때문에 이 지점부터 end()까지의 원소를 삭제할 수 있다.

위 함수에 대해서는 아래 사이트를 참고해서 공부했다.

https://m.blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=withham1&logNo=221102099316 

[C++] unique 함수를 이용한 vector 중복 제거

 

 

Code

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int n;
vector<int> v;
vector<int> tmp;
 
void comp(int num) //이진탐색 
{
    int high = v.size() - 1;
    int low = 0;
    int mid;
 
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (num == v[mid])
        {
            cout << mid << " ";
            break;
        }
        else if (num > v[mid])
            low = mid + 1;
        else
            high = mid - 1;
    }
}
 
int main()
{
    cin >> n;
    v.resize(n);
 
    for (int i = 0; i < n; i++)
        cin >> v[i];
 
    tmp = v; // v를 tmp에 복사
 
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end()); // v에서 중복원소 지우기
    
    for (int i = 0; i < tmp.size(); i++)
        comp(tmp[i]);
 
    return 0;
}