좌표 압축

18870번: 좌표 압축 (acmicpc.net)

 

솔직히 문제 자체는 무엇을 하라는 건지 이해가 잘 안된다.

다만, 예제로 보아 나열된 수열 x1, x2, x3.....   을 [0, 1, 2, 3.... ]의 범위로 재배치 하라는 듯 하다.

즉,  인덱스값으로 대체하라는 것 같다.

 

• 입력은 정렬되어 있지 않으니 먼저 복사후, 새 배열을 정렬한다.
• 그럼 가장 작은게 제일 앞에 있을 거고 인덱스가 0일 것이다.
• 중복 값을 빼서 입력값의 범위가 인덱스 범위와 1:1 매치 되도록 한다.
• 새 배열에 대해 입력 값 수열의 요소가 몇번째에 들어가는지(인덱스가 몇인지) 찾는다. (lower bound)

 

vector<int> Origin = { ... };

vector<int> newOrder(Origin);
sort(newOrder.begin(), newOrder.end());
newOrder.erase( unique(newOrder.begin(), newOrder.end()), newOrder.end());

for (const int& unit : Origin)
{
    auto iter = lower_bound( newOrder.begin(), newOrder.end(), unit);
    cout << iter - newOrder.begin() << ",";
}


// 인덱스 구할 때, distance(newOrder.begin(), iter) 도 가능.