백준 / 실버 2 / 18870 좌표 압축 / C++ [정렬, 맵, 해시]

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

첫 풀이

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, r, num;
    cin >> n;
    map<int, int> rank;
    vector<int> X(n);
    
    for (int i=0; i<n; i++){
        cin >> num;
        rank[num] = 0;
        X[i] = num;
    }
    r = 0;
    for (auto it = rank.begin(); it != rank.end(); it++) {
        rank[it->first] = r++;
    }
    for (int x : X) {
        cout << rank[x] << ' ';
    }
}

sort(), lower_bound()

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, i;
    cin >> n;
    vector<int> v(n);
    
    for (i=0;i<n;i++) cin >> v[i];
    vector<int> w(v);
    
    sort(w.begin(), w.end());
    w.erase(unique(w.begin(), w.end()), w.end());
    for (auto e : v) cout << (lower_bound(w.begin(), w.end(), e) - w.begin()) << " "; // 처음으로 e (이상이) 나오는 idx - 처음 idx == 순번
}

sort(v.begin(), v.end())

v.sort() 아님

v.erase(it1, it2)

[it1, it2) 가 제거된다

unique(it1, it2)

중복된 애들을 뒤로 옮기고 나머지 자리엔 기존 벡터배열 원소의 값

4 4 1 2 3 => 4 1 2 3 3

중복된 애들을 뒤로 옮기고, 중복이 시작되는 지점 (여기선 4번째, 마지막) iterator를 반환

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

중복 요소 삭제

vector<T> v1(n)

size n인 벡터 생성 (length = 0)

vector<T> v2(v1)

복사 생성

0, 1, 2, 3, 4

lower_bound(v.begin(), v.end(), 3);

처음으로 3 이상이 나오는 시점 => 3

upper_bound(v.begin(), v.end(), 3);

처음으로 3 초과가 나오는 시점 => 4

iterator 함수

*iter
iter++
iter--
iter1 == iter2
iter1 != iter2
begin(객체)
end(객체)