[C++] vector 정렬/안정정렬, vector 중복요소 제거, pair 자료형

pair 자료형

- utility 헤더 선언 필요, 그런데 <algorithm> 및 <vector> 헤더에 포함되어 있어 별도 선언 필요 x

    vector<pair<int, int>> v;

    int N, x, y;
    cin >> N;

    while(N--) {
        cin >> x >> y;
        v.push_back(make_pair(x,y));
    }

 

cf) python이었으면?

배열을 원소로 가지는 배열을 생성하면 되겠지

 

vector 정렬

- compare 함수를 별도로 정의하여 sorting 기준 명시

- compare 함수 파라미터로 const + &(참조, Referece) 조합 사용 // 상수성, 메모리 절약

bool compare(const pair<int, int>& p1, const pair<int, int>& p2) {
    if(p1.first == p2.first) return p1.second < p2.second;
    return p1.first < p2.first;
}

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

 

cf) python이었으면?

data_list.sort(key=lambda x : (x[0], x[1]))

// x[0]에 대해 오름차순 정렬하고, 동일 요소에 대해서는 x[1]에 대해 오름차순 정렬

data_list.sort(key=lambda x : (-x[0], x[1]))

// x[0]에 대해 내림차순 정렬을 할 수도 있다 (단 부호가 있는 자료형일 때)

data_list.sort(key=lambda x: x[1]) # x[1] 기준으로 오름차순 정렬
data_list.sort(key=lambda x: x[0], reverse=True) # x[0] 기준으로 내림차순 정렬

// sort()가 안정정렬 지원하므로 이렇게 두 번에 걸쳐서 정렬해도 됨

 

vector 중복 요소 제거

- vector 정렬된 상태여야 함 (중복된 요소들이 인접한 상태여야 함)

- unique 함수 실행 결과 unique list는 앞쪽으로/중복 요소들은 뒤쪽으로, 중복 요소들을 가리키는 포인터 리턴

- erase 함수 사용해 중복 요소 제거

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

 

cf) python이었으면?

data_list = list(set(data_list))

 

vector 안정 정렬

- 크기가 같은 원소들의 상대적 위치를 보존하려면 <algorithm> 헤더의 stable_sort 함수를 사용한다

    stable_sort(v.begin(), v.end(), [](const auto& p1, const auto& p2) { return p1.first<p2.first; });

 

cf) python이었으면?

python의 list.sort() 함수는 stable sort 이다 원래부터!!

 

이진 탐색

    sort(v2.begin(), v2.end());
    v2.erase(unique(v2.begin(), v2.end()), v2.end());
    
    for(int i=0; i<N; i++) {
        // cout << distance(v2.begin(), find(v2.begin(), v2.end(), v1[i])) << " "; // 시간 초과 원인
        cout << lower_bound(v2.begin(), v2.end(), v1[i])-v2.begin() << " ";
    }

- 이미 정렬되어 있는 list에서 binary_search() 함수 사용 시 true/false 리턴, lower_bound() 함수 사용 시 찾고자 하는 대상이 저장된 제일 작은 인덱스(의 주소) 리턴, upper_bound() 함수 사용 시 제일 큰 인덱스+1(의 주소) 리턴

 

cf) python이었으면?

- list.index() 함수는 선형 탐색을 하므로 O(n) 시간복잡도 가진다

- bisect 모듈의 bisect_left 함수를 사용해 이진 탐색을 할 수 있다, 단 정렬되어 있어야 함

import bisect

// 생략
num_set = sorted(list(set(num)))
for n in num:
    print(bisect.bisect_left(num_set, n), end=' ')