문제
풀이
algorithm 헤더의 unique 함수를 통해 쉽게 풀 수 있는 문제이다.
unique 함수
unique 함수는 연속으로 중복 되는 원소 를 vector의 제일 뒷부분으로 쓰레기 값으로 보낸다. 즉 다시 말해 중복 되지 않는 원소들 만을 앞에서 부터 채운다.
이때 주의할 점은 연속으로 중복 되는 원소만을 없애기 때문에 반드시 정렬 을 시행해 줘야 한다. 이제 그림을 통해 unique 함수를 알아보자.
아래와 같은 정렬된 벡터 v 가있다.
이 벡터에 unique 함수를 사용하면
1
unique(v.begin(),v.end())
-
연속으로 중복 되는 값 2, 4를 없앤다.
-
중복 되지 않는 값들을 앞에서 부터 채우며, 중복된 값이 사라져 남게 된 공간은 원본값을 유지한다.
-
unique 함수는 원본이 유지 된 원소들의 첫번째 주소 값을 반환한다.
-
최종적으로 erase 함수를 사용해 지워주면 중복 되지 않은 값들을 얻을 수 있다.
1
v.erase(unique(v.begin(),v.end()),v.end());
구현
- 원본 벡터를 입력 받고 원본벡터를 복사한 벡터를 만든다.
- 복사 벡터를 정렬한 후 unique함수로 중복 값을 제거해준다.
- 반복문으로 원본 벡터를 순서대로 확인한다.
- lower_bound 함수를 통해 원본 벡터의 i 번째 원소가 복사본 벡터에서 몇번째에 위치 하는지 확인한다(이때 lower_bound는 주소값을 반환).
- lower_bound의 반환 값에 시작 주소값을 빼준 값이 답이다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
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++)
{
// i번째 요소값의 위치 it
auto it = lower_bound(cv.begin(), cv.end(), v[i]);
// it에서 cv벡터의 시작 주소값을 빼준 값이 답
cout << it - cv.begin() << ' ';
}
return 0;
}
