수열 정렬하기 (JUNGOL 12494)

https://jungol.co.kr/problem/12494

---

아이디어

값 압축을 해서 0,1,2...K-1로 만들어둡시다.

 

만약 i이전에 등장하는 i+1이 있다면 i를 한번은 선택해야합니다. 그렇지 않다면 i를 선택할 필요가 없습니다. 그러므로 i이전에 등장하는 i+1이 있는지의 여부 Select[i]를 다 저장해준 다음 그 개수를 세어주면 됩니다.

---

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

ll arr[303030]={0};
vector <ll> nums;
bool ck[303030]={0};
bool Select[303030]={0};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,i,cnt=0;

    cin>>N;
    for (i=0;i<N;i++)
    {
        cin>>arr[i];
        nums.push_back(arr[i]);
    }
    sort (nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    for (i=0;i<N;i++)
    {
        arr[i]=lower_bound(nums.begin(),nums.end(),arr[i])-nums.begin();
        ck[arr[i]]=true;
        if (ck[arr[i]+1]) Select[arr[i]]=true;
    }
    for (i=0;i<nums.size();i++)
        if (Select[i])
            cnt++;

    cout<<cnt;
}