LeetCode [1331]: Rank Transform of an Array

📌 LeetCode [1331]: Rank Transform of an Array

🔗 문제 링크

---

문제 설명 📄

주어진 배열 arr의 각 요소를 랭크(Rank)로 변환해야 합니다.
랭크는 다음과 같은 규칙에 따라 정의됩니다:

1. 배열의 고유 요소들을 정렬합니다.
2. 정렬된 순서에 따라 각 고유 요소에 1부터 시작하는 랭크를 할당합니다.
3. 원래 배열의 각 요소를 해당 랭크로 대체하여 반환합니다.

---

문제 접근 방식 📋

1. 중복 제거 및 정렬:
   • set을 사용해 고유 요소를 추출한 뒤, 정렬하여 각 요소에 랭크를 할당합니다.
2. 맵핑 생성:
   • 정렬된 요소를 기준으로 {값: 랭크} 형태의 딕셔너리를 생성합니다.
3. 랭크 변환:
   • 원래 배열의 각 요소를 딕셔너리를 참조해 랭크로 변환합니다.

---

Solution 💻

class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        pattern = {key: index + 1 for index, key in enumerate(sorted(set(arr)))}

        answer = []
        for i in arr:
            answer.append(pattern[i])

        return answer

시간 복잡도 ⏲️

• 중복 제거 및 정렬: (O(n log n)), (n)은 배열의 길이.
• 딕셔너리 생성: (O(k)), (k)는 고유 요소의 개수.
• 배열 순회 및 변환: (O(n)).
• 최종 시간 복잡도: (O(n log n)).

공간 복잡도 🗄️

• 딕셔너리 저장 공간: (O(k)), 고유 요소의 개수.
• 최종 공간 복잡도: (O(k + n)).

---