출처 : 백준
문제 보러가기 : 좌표 압축
좌표 압축 문제는 각각의 좌표보다 작은 값들의 개수를 알아내는 비교적 단순한 문제이다.
해당 문제는 정렬과 lower_bound함수를 사용해서 해결할 수 있었다.
해결
1. 우선적으로 좌표 입력 순서를 담는 vector V와 정렬 용도의 vector S를 각각 생성한다.
2. S를 Algorithm STL이 제공해주는 sort함수를 이용하여 정렬 후 unique함수로 중복되는 원소를 제거해준다.
-> 주의 : unique함수는 정렬 후 사용해야 한다.
3. S에 대해서 lower_bound 함수를 통해 V에 저장된 각각의 좌표 순서대로 주소를 가져온 후 S의 시작 주소를 빼준 값을 출력한다.
-> 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
#include
#include
using namespace std;
int main() {
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
int n, x;
vector v; // 입력 순서 저장
vector s;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> x;
v.push_back(x);
s.push_back(x);
}
sort(s.begin(), s.end());
s.erase(unique(s.begin(), s.end()), s.end());
for (int i = 0; i < n; i++) {
int temp = lower_bound(s.begin(), s.end(), v[i]) - s.begin(); // 좌표의 위치 - 시작 주소 = 좌표보다 작은 서로다른 좌표들의 개수
cout << temp << " ";
}
return 0;
}
|
cs |
댓글