좌표 압축
요즈음은 그냥 solved.ac에서 클래스별로 문제를 풀고 있는데
현재 티어까지 지나온 길을 확인하던 중
내가 틀렸던 문제가 있길래 확인을 해봤다.
신기하게도 ps에 C++을 사용하는 내가
python으로 문제를 한 번 제출해서 틀렸었다. 무슨일일까..?
문제는 여튼
주어진 숫자들에 대해 대소관계를 유지하는게 핵심이다.
전체 리스트에 대소관계라.. 생각하자마자
바로 정렬이 떠오른다.
문제에서 주어지는 수가 최대 100만 이므로
stl 정렬에서 사용되는 n * lg n 시간복잡도를 이용해도
간단히 대소관계의 정립을 끝낼 수 있다.
물론, 주어진 예시처럼 중복된 숫자들의 경우를 처리하는게
또 하나의 관건인데
내가 생각하기엔 중복을 없엔다면, 정렬된 배열의 인덱스 자체가
압축된 수 일거라고 생각해서
중복을 없에는 것에 초점을 맞췄다.
사실 중복을 없에는 것도 간단하다.
unique()를 이용하면 된다.
unique는 보통 이렇게 쓴다.
vector<int> v; //임의의 vector v가 존재한다고 가정
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());왜 그렇냐면
일단 정렬을 해 주면
[1,3,2,1,3,2,1] 이라는 배열을 가정했을 때
[1,1,1,2,2,3,3] 이 될 것이다.
이 상태에서, unique를 하면
[1,2,3]을 만들고 그 다음 중복이 시작될 위치를 반환해준다.
그래서 그 뒤의 중복이 시작되는 위치 ~ 끝 까지를
erase 해 주는 것이다.
이것을 통해 vector의 중복을 제거할 수 있다.
여튼 이렇게 벡터의 중복이 제거됐다면,
이제 특정 값에 대해 그 값이 unique해진 vector에서의 index값을 얻어내면 그게 압축된 좌표이다.
여기서도 하나 포인트가 있다.
그냥 단순히 전체를 조회해버리면
각 원소당 vector를 조회해야 하고 이 경우 시간복잡도는 n^2,
최대 조회 횟수는 1000000^2가 된다.
제한시간 2초를 아득히 넘어버린다.
그러면 우리는 뭘 사용해야 하느냐
특정 값이 존재하는지, 안하는지, 존재한다면 어디있는지 빨리 찾는
그런 알고리즘,
그렇다. 이진탐색(binary search)를 사용하자
심지어 우리는 중복만 제거했을 뿐 이므로 주어진 모든 원소들은
적어도 한 번 이상 unique해진 vector에 존재함을 알고 있다.
딱히 원소가 없을 경우를 판단하지 않고,
무조건 찾을 수 있다는 가정으로 이진탐색을 돌리면 된다.
그렇게 하면 전체 원소 n에 대해 이진탐색 lg n을 시행하므로
총 시간복잡도는 n*lg n이다. 위의 정렬에서와 마찬가지로
충분히 문제를 해결할 수 있다.
코드는 다음과 같다.
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> v;
vector<int> v2;
int bs(int x);
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
int k;
cin>>k;
v.push_back(k);
v2.push_back(k);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
for(auto x : v2){
cout<<bs(x)<<" ";
}
return 0;
}
int bs(int x){
int left= 0;
int right = v.size()-1;
while(left<=right){
int mid = (left+right)/2;
if(v[mid]==x){
return mid;
}
else{
if(v[mid]<x){
left=mid+1;
}
else{
right=mid-1;
}
}
}
return 0;
}