[LeetCode] 1331. Rank Transform of an Array

https://leetcode.com/problems/rank-transform-of-an-array/description/?envType=daily-question&envId=2024-09-27

leetcode - Rank Transform of an Array

문제 유형 : 정렬, 이진 탐색

문제 난이도 : Easy

 

문제

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

• Rank is an integer starting from 1.
• The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
• Rank should be as small as possible.

정수 배열 arr이 주어진다.

순위를 매겨서 대체하시오.

rank는 요소가 얼마나 큰지를 나타냅니다.

Rank는 1부터 시작해서, 더 큰 요소가 더 큰 rank를 가집니다.

동등하면 같은 랭크를 가집니다.

Rank는 최대한 작아야 합니다.

 

풀이

배열 arr의 복사본을 하나 만들어서, 중복 제거를 시키고 정렬시킨다.

그 뒤, arr을 순차적으로 순회하면서 정렬된 배열에서 이진 탐색으로 인덱스를 찾아서 +1해서 랭크를 매겨준다.

 

std::set은 내부적으로 레드블랙트리를 쓰는데, 이는 메모리 오버헤드가 있고, 중복이 있는지에 대한 여부를 트리 탐색에서 찾아서 더 느릴 수 있어서 TLE에 걸릴 수 있다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
private:
    int binSearch(vector<int>& arr, int num) {
        int left = 0;
        int right = arr.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == num) return mid;

            if (arr[mid] > num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return -1;
    }
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        vector<int> sorted(arr.begin(), arr.end());

        sort(sorted.begin(), sorted.end());
        sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());

        vector<int> ans;
        for (const auto& num : arr) {
            ans.push_back(binSearch(sorted, num) + 1);
        }

        return ans;
    }
};