LeetCode [2053]: Kth Distinct String in an Array

📌 LeetCode [2053]: Kth Distinct String in an Array

🔗 문제 링크

---

문제 설명 📄

주어진 문자열 배열 arr에서 고유한 문자열(distinct string) 중 k번째 문자열을 반환합니다. 고유한 문자열은 배열에서 한 번만 등장하는 문자열입니다.

• k번째 고유 문자열이 존재하지 않으면 빈 문자열 ""을 반환합니다.

---

문제 접근 방식 📋

1. 문자열 빈도 계산:
   • Counter를 사용해 배열 arr에서 각 문자열의 빈도수를 계산합니다.
2. 순서 유지:
   • 등장 순서대로 문자열을 저장하기 위해 OrderedDict를 사용합니다.
   • 빈도수가 1인 문자열만 OrderedDict에 저장합니다.
3. k번째 문자열 반환:
   • OrderedDict의 키를 리스트로 변환해 인덱스를 통해 k번째 문자열을 찾습니다.

---

Solution 💻

from collections import Counter, OrderedDict

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        count = Counter(arr)
        ordered_count = OrderedDict((key, val) for key, val in count.items() if val == 1)

        if len(ordered_count) >= k:
            return list(ordered_count.keys())[k-1]
        return ""

---

시간 복잡도 분석 ⏲️

• Counter 빈도 계산: O(n) – n은 배열의 길이입니다.
• OrderedDict 생성: O(n) – 빈도수가 1인 문자열을 필터링하는 과정입니다.
• k번째 요소 접근: O(k) – 고유한 문자열 리스트에서 k번째 요소를 반환합니다.
• 총 시간 복잡도: O(n)

공간 복잡도 분석 🗄️

• Counter와 OrderedDict: O(n) – 최대 n개의 문자열을 저장합니다.
• 결과 리스트: O(k) – k번째 요소를 찾기 위해 리스트를 생성합니다.
• 총 공간 복잡도: O(n)

---