18870

좌표 압축

 

첨엔 알고리즘의 find 함수를 썼는데 시간초과가 났다.. 흑흑

 

그 대신 unique라는 좋은 함수를 알아냈다..

연속된 수 중 중복인 숫자는 하나를 제외하고 없앤다.

꼭 연.속 된 숫자여야 한다!!

처음에 지워버리는게 아니라 중복된 숫자를 배열의 맨 뒤로 보내고 뒤로 보낸 숫자중 첫 원소의 주소를 return 한다

따라서 그 중복 숫자열을 지워주는 과정까지 해주면.. 완성이다

 

copy.erase(unique(copy.begin(), copy.end()), copy.end());

 

#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;

int binary_search(vector<int >& num, int digit);

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
    vector<int>num(n);
	for (int i = 0;i < n;i++) {
        cin >> num[i];
	}	

	vector<int>copy(num);
	sort(copy.begin(), copy.end());

	copy.erase(unique(copy.begin(), copy.end()), copy.end());

	for (int i = 0;i < n;i++) {
		cout<<binary_search(copy,num[i]) << " ";
	}

	return 0;
}

int binary_search(vector<int >&num,int digit)
{
    int ind_end = num.size() - 1;
    int ind_beg = 0;
    while (ind_end - ind_beg > 1)
    {
        int index = ind_beg + (ind_end - ind_beg) / 2;
        if (digit < num.at(index))
        {
            ind_end = index;
        }
        else if (digit > num.at(index))
        {
            ind_beg = index;
        }
        else
        {
            return index;
        }

    }
    if (num.at(ind_end) == digit )
    {
        return ind_end;
    }
    if (num.at(ind_beg) == digit)
    {
        return ind_beg;
    }
    return 0;
};