[Leetcode][2306][Hard] Naming a Company

문제

2306번 문제 링크

Enumeration과 Set을 잘 이용하면 쉽게 풀 수 있는 문제이다.
Hard 중에서는 이렇게 아이디어를 보는 문제도 나오는데, 재밌고 참신한 것 같다.
간단히 정리하면, List에 있는 단어들로 쌍을 만들어서 새로운 단어를 만드는데,

각 단어의 앞 문자만 서로 바꿔서 쌍을 만드는 것이다.
이 때, 바뀐 단어가 기존의 List에 들어있지 않은 쌍의 갯수를 출력하는 것이 목표이다.
List의 길이는 2 <= ideas.length <= 5 * 10^4 이다.

풀이

요새는 솔루션을 참고하는 나쁜 버릇이 자꾸 생기고 있다.
처음 접근은 시간 복잡도가 이중 루프를 구성하면 시간 초과가 걸릴 쯔음 되어 보여서
어떻게는 단일 루프로만 풀려고 생각했었다.
기본적으로는 앞 글자는 총 26자 일테니, 각 알파벳에 포함되는 단어의 set을 dictionary로 만들었다.

하나의 set에 있는 단어들을 List에 있는 앞 글자 루프를 돌면서 새로 단어를 조합하고,
이 단어가 기존의 List에 있는지를 검사하였다.
이렇게 하면 문제점이 단 방향의 단어만 검색 가능하다는 것이다.
무슨 말이냐면, coffee에 t를 조합하여 toffee가 List에 있는지는 알겠지만,
c와 어떤 단어를 조합하는지는 찾아지지 않는다.

결국, 아이디어가 잘 안돌아서 솔루션을 참고했고, 참 간단하고 심플한 코드를 작성할 수 있었다.
일단, 앞 글자 별 set을 만드는 것 까지는 좋은데, set 끼리 비교를 하면서
겹치는 뒷 단어(앞 글자를 제외한 단어)를 뺀 나머지 단어 갯수 끼리의 곱 * 2를 하면 된다.

정리하면 c: {coffee, comic}, t: {toffee, time, table} 이 있다면
여기서 offee는 양쪽 set에 있기 때문에, 다른 set에 있는 단어와 조합해도
무조건 내 set에 포함되게 되므로 무조건 빼는 것이다.
위 예시로 보면 c set에는 comic이 유일하고, t set에는 time, table이 유일하다.
문제 조건에 따라 쌍은 앞 뒤가 바뀌어도 되므로, 1개 (comic) * 2개 (time, table) * 2 (앞 뒤 교환) 이 된다.

아, 그리고 시간복잡도는 사실 앞 글자 별로 이중 루프를 돌면 되어서
(25 * 24) / 2 가 된다.

def distinctNames(self, ideas: List[str]) -> int:
    from collections import defaultdict
    count = 0

    cs = defaultdict(set)
    for idea in ideas:
        cs[idea[0]].add(idea[1:])

    while len(cs) > 0:
        a = cs.popitem()[1]
        for c in cs:
            n = len(a - cs[c])
            m = len(cs[c] - a)
            count += n * m * 2

    return count

회고

1. Hard 문제라고 쫄 것은 없다.
2. 참신한 아이디어를 위해 조금 더 돌려보고, 생각해보자.
3. 왜 안되는 경우가 생기는지르 직접 적거나 그려봤으면 답에 더 가까웠을 것 같다.