[알고리즘] 배열의 데이터 압축하기

- 벡터를 활용해서 압축 하는 방법

    vector <int> compress;
    for(int i=1;i<=n;i++)
    {
        cin >> player[i];
        compress.push_back(player[i]); //player[i]를 압축하자.
    }
    sort(compress.begin(),compress.end());
    compress.erase(unique(compress.begin() , compress.end()),compress.end()); //같은 숫자는 삭제

    for(int i=1;i<=n;i++){
        player[i]= lower_bound(compress.begin(), compress.end(), player[i]) - compress.begin();
    }

위와 같이 player 의 큰 값을 compress 의 순서대로 정렬해서 같은 수는 모두 삭제해서 없애고

compress에 들어 있는 위치의 값을 player의 값으로 사용하게 되면 player의 값은 n 개 보다 작은 값만 가지게 된다.

 

- 맵을 활용해서 압축하는 방법

    for(int i=2; i<=n; i++){
        arr[i]=(m*arr[i-1]+c)%(long long int)0x7fffffff;
        sarr[i]=arr[i];
    }
    sort(sarr+1, sarr+n+1);
    for(int i=1; i<=n; i++){
        M[sarr[i]]=i;
    }
    for(int i=1; i<=n; i++){
        arr[i]=M[arr[i]];
    }

배열을 복사 한 후 복사한 배열을 정렬 하여 해당 숫자를 키값으로 하는 맵의 값에 자신의 숫자를 기록 한 후에 해당 순서를 바꿔주는 형식을 취해도 된다.

맵 역시 이진트리 형식이라서 조회가 빠르다.

 

둘 중 어느 형식으로 압축을 해도 가능