[2024] day 219. Leetcode 2053. Kth Distinct String in an Array

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 8월 5일 (월)
Leetcode daily problem

2053. Kth Distinct String in an Array

https://leetcode.com/problems/kth-distinct-string-in-an-array/?envType=daily-question&envId=2024-08-05

Problem

고유한 문자열이 배열의 요소로 있는 문자 배열이 주어지고 정수 k가 주어 질때, 배열에서 k번째로 고유한 문자열을 반환하고 반환할 문자열이 없다면 ""를 반환한다.

문자열의 order(순서)는 배열에 나타나는 순서이다.

Solution

Hash map

문자열의 발생 빈도를 저장하는 map을 만들고,
빈도가 1인 경우에 고유한 것으로 판단할 수 있다.

주어진 배열을 한 번 순회하면서 문자열의 빈도열을 저장하고,
저장한 map을 순환하면서 고유한 문자열을 찾을 때마다 k를 감소시키고, k가 0에 도달하면 현재 문자열을 반환한다.
0에 도달하기 전에 문자열이 끝나면 ""를 반환한다.

Code

class Solution:
    def kthDistinct(self, arr: List[str], k: int) -> str:
        freq_map = {}
        
        for c in arr:
            freq_map[c] = freq_map.get(c,0) +1
            
        for c in arr:
            if freq_map[c] == 1:
                k -=1
            
            if k==0:
                return c
            
        return ""

Complexicity

시간 복잡도

주어진 배열을 순환하면서 배열의 빈도수를 저장할 때 시간복잡도 O(n)이 소요된다.
빈도수를 저장한 배열을 순환하면서 k를 가감하는 과정에서도 배열을 한 번더 순환하여 O(n)이 소요되므로 최종 시간 복잡도는 O(n) + O(n) = O(n) 이다.

공간 복잡도

배열을 돌면서 빈도수를 저장하는 freq_map는 배열의 길이 n에 비례하고 고유한 요소를 키로 가지고 각 키의 빈도를 값으로 저장한다. 해당 공간복잡도는 O(n) 이고, 나머지는 상수 공간을 차지하기 때문에 총 공간복잡도는 O(n) 이다.