[백준 18870] 좌표 압축

www.acmicpc.net/problem/18870

18870번: 좌표 압축

이걸 대체 어케 아는걸까...

 

인덱스와 값을 사용해서 푸는 문제이다.

정렬까진 알았는데 어떻게 활용해야 할지는 답을 봤다ㅠㅠ

 

로직은 다음과 같다.

값을 기준으로 오름차순 정렬된 배열을 돌면서 그 값의 인덱스에 해당하는 배열에 cnt값을 넣는다.

1. 인덱스와 값을 저장

2. 값을 기준으로 오름차순 정렬

3. 배열을 순회하며 해당 인덱스에 cnt값을 집어 넣는다.

3-1. 이때 cnt는 값이 달라질 때마다 ++되므로 값보다 작은 숫자의 개수라고 할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int n;
vector<pair<int, int>> v;
vector<int> ans(1000001);
int main(void)
{
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);

  cin >> n;

  for (int i = 0; i < n; i++)
  {
    int x;
    cin >> x;
    v.push_back({x, i});
  }

  sort(v.begin(), v.end());

  int cmp = v[0].first;
  int cnt = 0;
  ans[v[0].second] = 0;

  for (int i = 1; i < n; i++)
  {
    if (cmp == v[i].first)
    {
      ans[v[i].second] = cnt;
    }
    else
    {
      ans[v[i].second] = ++cnt;
      cmp = v[i].first;
    }
  }

  for (int i = 0; i < n; i++)
  {
    cout << ans[i] << " ";
  }

  return 0;
}