이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 57 번째 글 입니다.
목차
실버2 : 파라메트릭 서치 문제이다.
Root 찾기
처음에 또다시 해시로 풀려고 하다가, 중간에 입력값의 범위가 후덜덜한 것을 보고 풀이 방법을 바꾸었다. 이 문제를 그냥 linear하게 풀려고 하면 100000번을 linear하게 탐색해야 하기 때문에 터져버린다.
그래서! 이 문제는 파라메트릭 서치로 풀이한다. 하나의 질문에 대해 몇번이 필요한지 사실 결정되어 있다. 입력되는 것들을 집합화 하고, 이것들을 정렬하면, index가 곧 해당 입력의 압축된 좌표이다.
- 입력
5
2 4 -10 4 -9
| 집합화 | 2 | 4 | -10 | -9 |
|---|---|---|---|---|
| 정렬 | -10 | -9 | 2 | 4 |
| index | 0 | 1 | 2 | 3 |
잘 보면, 집합화 한 원소를 정렬한 뒤, 이것들을 배열에 넣었을 때, index가 곧 해당 원소의 압축된 좌표이다.
따라서, 이제는 입력된 순서대로 이 index를 찾아주기만 하면 된다. 이 때, 찾는 방법으로 이진 탐색을 사용하면 된다.
Code
#include <iostream>
#include <set>
using namespace std;
int N;
set<int> s;
int arr[1000001];
int net[1000001];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> arr[i];
s.insert(arr[i]);
}
int idx = -1;
for (auto iter = s.begin(); iter != s.end(); iter++) {
idx++;
net[idx] = *iter;
}
for (int i = 0; i < N; i++) {
int start = 0, end = idx;
int now = arr[i];
while (start <= end) {
int mid = (start+end)/2;
if (net[mid] > now) {
end = mid-1;
} else if (net[mid] < now){
start = mid+1;
} else {
cout << mid << " ";
break;
}
}
}
return 0;
}