18870: 좌표 압축 (acmicpc.net)
문제
수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.
X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.
입력
첫째 줄에 N이 주어진다.
둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.
출력
첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.
제한
1 ≤ N ≤ 1,000,000
(-10)^9 ≤ Xi ≤ 10^9
예제 입력 1
5
2 4 -10 4 -9예제 출력 1
2 3 0 3 1풀이
coordinates, sorted 벡터에 각각 좌표를 입력받는다. coordinates 벡터는 원본으로, sorted는 정렬하여 사용할 것이다.
자신보다 작은 좌표의 개수를 세는 것이므로, 오름차순 정렬하여 중복을 제거하였을 때, 해당 좌표보다 앞의 있는 좌표들의 개수 (= 해당 좌표의 인덱스)를 알면 된다.
unique(a, b)를 사용하면, a부터 b까지의 범위 중에서, 연속하는 중복된 값을 지우고 앞에서부터 값을 채운다. 두 개의 포인터를 이용하는 함수이기 때문에, unique를 사용하려면 정렬된 상태여야 한다.
값을 앞에서부터 채우므로, 예시에서 뒤의 2 3 4는 필요 없는 값이다. 따라서 erase를 이용해서 지워줄 것인데, unique는 쓰레기값의 첫 번째 위치를 반환하므로, erase의 시작 값에 unique를 넣어주면 코드를 간략화할 수 있다.
이제 coordinates 벡터의 모든 인덱스를 돌면서, 그 인덱스의 값이 sorted 벡터의 몇 번째 인덱스에 있는지 확인하면 된다. 선형 탐색을 하면 시간이 오래 걸리므로, lower_bound 함수를 사용하였다.
lower_bound(begin, end, key) 는 이진탐색을 실행하여, key값보다 크거나 같은 값 중 가장 작은 값의 위치를 반환한다. index가 아닌 메모리 위치를 반환하기 때문에, index를 구하려면 반환된 메모리 위치에서 벡터의 시작 위치를 빼주면 된다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> coordinates;
vector<int> sorted;
int n;
void set_io(void);
void input_data(void);
void compress(void);
int main(void)
{
set_io();
input_data();
compress();
return (0);
}
void set_io(void)
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
return ;
}
void input_data(void)
{
cin >> n;
int i = -1;
while (++i < n)
{
int input;
cin >> input;
coordinates.push_back(input);
sorted.push_back(input);
}
return ;
}
void compress(void)
{
sort(sorted.begin(), sorted.end());
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
int sorted_length = sorted.size();
int i = -1;
while (++i < n)
cout << lower_bound(sorted.begin(), sorted.end(), coordinates[i]) - sorted.begin() << ' ';
return ;
}
성공❤
