백준 18870 - 좌표 압축(C++)

문제

https://www.acmicpc.net/problem/18870

18870번: 좌표 압축

 

풀이

n개의 숫자 중에서 자신보다 작은 수의 개수를 하나씩 출력하는 문제이다.

처음에는 set을 사용하여 풀이하려고 시도했다.

set에 입력받은 수를 insert 하면 정렬이 되고, 중복이 제거되므로

for문을 돌면서 작은 수들의 개수를 세려고 했지만 시간 초과가 발생했다.

set이나 map은 정렬과 중복 제거가 수행되지만 인덱스로 접근할 수 없으므로

벡터를 이용했고 이분탐색으로 풀이했다.

 

이때 벡터에서 중복을 제거하기 위해 erase를 해줄 때, 먼저 sort가 수행되어야 한다.

unique 함수는 앞과 뒤의 원소를 비교하기 때문에 정렬된 상태여야 제대로 수행된다.

 

코드

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

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

    int n;
    cin>>n;

    vector<int> v;
    vector<int> v2;
    int cnt=0;

    for(int i=0; i<n; i++)
    {
        int a;
        cin>>a;
        v.push_back(a);
        v2.push_back(a);
    }
    sort(v2.begin(),v2.end());
    v2.erase(unique(v2.begin(),v2.end()),v2.end());
    for(int i=0; i<n; i++)
    {
        int start=0;
        int end = v2.size()-1;
        int mid;
        bool flag=false;
        while(start<=end)
        {
            mid = (start+end)/2;
            if(v2[mid]>v[i]) end=mid-1;
            else if(v2[mid]<v[i]) start = mid+1;
            else 
            {
                cout<<mid<<' ';
                flag=true;
                break;
            }
        }
        if(!flag) cout<<0<<' ';
    }
}