unique함수는 연속으로 중복되는 원소를 제거하는 함수이다.
구체적인 작동방법은 다음과 같다.
v=3 4 4 2 1 2 5 일때 v를 sort 함수를 통해서 정렬하면
v=1 2 2 3 4 4 5 이고 unique함수에 넣으면 연속으로 중복되는 원소들이 사라지고 남은 원소들을 앞에서부터 순서대로 채워넣고 남은 자리에는 원본의 원소를 그대로 가져다가 쓴다.
v = 1 2 2 3 4 4 5 에서
unique(v.begin(), v.end());하면 v = 1 2 3 4 5 4 5가 된다. 이제 원본의 원소를 그대로 가져다가 쓴 부분만 지우면 중복된 원소가 하나도 없는 정렬이 완성되는데 unique 함수는 원본의 원소를 그대로 쓴 첫번째 주소를 반환하기 때문에
v.erase(unique(v.begin(), v.end()),v.end());를 실행하면 v = 1 2 3 4 5가 됨을 알 수 있다.
lower_bound는 이진 탐색으로 원소를 탐색하는 함수이다. 탐색을 진행하려는 정렬이나 vector가 정렬 되어 있어야 사용할 수 있으며 lower_bound의 용도는 찾으려는 key값보다 같거나 큰 숫자가 배열의 몇번째에서 처음 등장하는지 찾기 위해서이다.
사용 예시를 들면 다음과 같다.
int arr = {1, 2, 3, 4, 5, 6};
cout << "lower_bound(6) :" << lower_bound(arr, arr+6, 6) - arr;이 경우 출력 값은 lower_bound(6) : 5이다.
lower_bound의 반환형은 Iterator이므로 실제로 배열에서 몇번째 인덱스인지 알려면 배열 주소의 이름(=배열의 시작 주소값)을 빼주어야 한다.
vector에서는
lower_bound(arr.begin(), arr.end(), 6) - arr.begin()의 형태로 사용한다.
upper_bound도 사용법과 작동법은 같지만 key값을 처음으로 초과하는 배열이나 vector의 인덱스 값을 반환한다는 차이가 있다.
이러한 배경 지식을 바탕으로 백준18870번을 아래와 같은 코드로 제출하였다.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n); // 원본 벡터
for (int i = 0; i < n; i++) {
cin >> v[i];
}
vector<int> cv(v); // 벡터의 복사본
sort(cv.begin(), cv.end());// 오름차순 정렬
cv.erase(unique(cv.begin(), cv.end()), cv.end());
//연속으로 중복되는 숫자들을 없애고 뒤에 쓰래기 값을 지움
for (int i = 0; i < n; i++) {
cout << lower_bound(cv.begin(), cv.end(), v[i]) - cv.begin() << ' ';
}
} 2021/09/23