[C++] 백준 18870 - 좌표 압축

🔐 백준 18870 - 좌표 압축

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

🔑 풀이

문제가 수식으로 주어져 있어 이해하기 어려울 수 있지만, 주어진 각각의 수보다 작은 숫자의

개수를 중복을 제외하고 몇 개인지 묻는 문제이다. 처음에는 주어진 수들을 정렬하고, set 자료구조를

이용하여 중복을 제거하고, lower_bound 함수를 통해 개수를 구하려고 했다.

// 틀린 풀이

int n;
int arr[1000001];
vector<int> ans;

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

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> arr[i];

    vector<int> v(arr, arr+n);
    sort(v.begin(), v.end());

    for (int i = 0; i < n; ++i) {
        set<int> s(v.begin(), lower_bound(v.begin(), v.end(), arr[i]));
        cout << s.size() << ' ';
    }

    return 0;
}

하지만, 시간초과로 인해 해결하지 못했고, 중복 제거가 선행되야 될 것 같다는 생각을 하게 되었다.

중복 제거를 위해 erase와 unique 함수를 사용하여 쉽게 해결할 수 있었다.

🧩 코드