[백준] 18870번 좌표압축 -C++

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

18870번: 좌표 압축

stl vector에 대해서 더 공부할 수 있던 문제였다.

 

처음엔 vector<pair<int, int>> v로 선언해서 {X, 순서}를 저장하려고 했는데, 풀다보니까 순서를 굳이 저장할 필요가 없어져서 vector<int> v로 바꾸어 풀었다.

 

참고로 pair로 선언된 vector를 sort함수로 정렬할때 compare함수를 따로 작성안하면 first 값을 기준으로 정렬 된다고함!!

vector

unique 함수

unique 함수는 <algorithm>헤더에 포함되어 있으며, vector의 중복된 원소를 제거할 때 사용할 수 있는 함수이다.

ForwardIterator unique (ForwardIterator first, ForwardIterator last);

 

사용할때는 vector가 정렬된 상태여야 한다.

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

int main(void){
    vector<int> v = {9, 5, 3, 4, 4, 3, 2, 1, 5, 5, 6};

    sort(v.begin(), v.end());
    unique(v.begin(), v.end());
    for(auto c : v){
        cout << c << ' '; 
    }   //1 2 3 4 5 6 9 5 5 6 9 출력
    
}

 

위의 결과를 보면 중복된 수는 뒤쪽에 저장되는데, unique 함수는 이 중복된 수의 시작주소를 반환한다.

erase 함수와 같이 사용하면 뒤쪽 중복된 원소들을 지울 수 있다.

 

erase 함수

erase 함수는 vector 컨테이너에 포함되며, vector의 특정 범위의 원소를 지울때 사용할 수 있다.

iterator erase (const_iterator position);	//단일 위치를 지우는데 사용
iterator erase (const_iterator first, const_iterator last);	//[first, last)를 지우는데 사용

 

unique 함수와 연계하면 다음과같이 사용가능하다.

이때의 first 인자는 v벡터에서 unique함수가 반환한 중복되는 값의 시작점이 되며, erase 함수를 이용해 v에서 중복된 값들을 삭제한다.

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

 

lower_bound, upper_bound함수

<algorithm> 헤더에 포함되어있다.

이진탐색에 기반하므로 오름차순으로 벡터가 정렬되어 있어야 사용할 수 있다.

ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val);

두 함수는 조금 비슷한데,

lower_bound 함수는 val보다 작지 않은(==크거나 같은) [first, last)범위의 첫번째 요소를 가리키는 반복자를 반환한다.

upper_bound 함수는 val보다 큰 [first, last) 범위의 첫번째 요소를 가리키는 반복자를 반환한다.

 

반환되는 iterator에서 vector의 첫번재 원소를 가리키는 주소인 v.begin()을 빼면 인덱스를 만들수 있다.

만약 v 벡터의 k값의 인덱스를 찾고자 한다면,

lower_bound(v.begin(), v.end(), k) - v2.begin();

 

최종 코드

#include <bits/stdc++.h>
using namespace std;

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    vector<int> v;
    int N;
    cin >> N;
    for(int i = 0; i < N; i++){
        int X;
        cin >> X;
        v.push_back(X); 
    }
    
    vector<int> v2 = v;	//벡터를 복사
    sort(v2.begin(), v2.end());	//오름차순 정렬
    v2.erase(unique(v2.begin(), v2.end()), v2.end());	//중복되는 원소 제거
    for(int i = 0; i < N; i++){
        cout << lower_bound(v2.begin(), v2.end(), v[i]) - v2.begin() << ' '; //인덱스메겨서 출력
    }

}