[LeetCode] 2306. Naming a Company

- Problem

2306. Naming a Company

Hard 난이도 치고는 문제를 이해하거나 풀이 방법을 생각해내는 데에 어려운 부분은 없다.

---

- 내 풀이 1 (Brute-force, TLE)

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        N = len(ideas)
        target = set(ideas)
        answer = 0

        for i in range(N-1):
            for j in range(i+1, N):
                str1, str2 = ideas[i][0] + ideas[j][1:], ideas[j][0] + ideas[i][1:]
                if str1 not in target and str2 not in target:
                    answer += 2
        
        return answer

- 결과

• 시간 복잡도: O(N^2)
• 공간 복잡도: O(N)

문제를 주어진 그대로 풀이해보자면 위의 코드가 된다. 심플하다.
하지만, TLE가 나는 데에는 이유가 있다(난이도가 Hard인 데에는 이유가 있다).

---

- 내 풀이 2 (Hash)

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        words = defaultdict(set)
        answer = 0

        for idea in ideas: # O(N)
            key = ord(idea[0]) - ord('a')
            words[key].add(idea[1:])

        for i in range(25):
            if i in words:
                for j in range(i+1, 26):
                    if j in words:
                        len1, len2 = map(len, (words[i], words[j]))
                        not_duplicated_words = len(words[i] & words[j]) # O(min(len(words[i), len(words[j)))
                        answer += (len1 - not_duplicated_words) * (len2 - not_duplicated_words)
       
        return answer * 2

- 결과

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