Kth Distinct String in an Array

•

문제 링크 : LeetCodeKth Distinct String in an Array - LeetCode

•

문제 설명 : 제공된 단어 중, N번째로 고유한 단어를 반환

•

풀이 방법

◦

각 단어가 주어진 arr 에서 몇번 등장하는지 확인

•

시간복잡도 : O(N)O(N)O(N)

•

성공 코드

from collections import defaultdict

# O(N + N) -> O(N)
class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        count_info = defaultdict(int)
        word_keys = []
        
        # 각 단어의 존재 갯수를 확인
        # O(N)
        for word in arr:
            if not count_info.get(word):
                word_keys.append(word)

            count_info[word] += 1
        
        # k번째로 고유한 단어 찾기
        # O(N)
        for i, v in enumerate(word_keys):
            if count_info[v] == 1:
                k -= 1

                if k == 0:
                    return v

        return ""
Python
복사