[python3] 2306. Naming a Company

풀이 일자: 23.02.09

난이도: [Hard]

분류: [Array, Hash Table, Bit Manipulation]

문제 내용

사명의 후보가 될 단어들을 ideas라는 배열안에 주어지고 이 중 2개를 선택하여 사명을 지으려고 하며 이때 사명의 조건은

2개의 다른 단어들을  배열에서 뽑아서 서로 앞의 알파벳을 바꿨을 때 바꾼 단어가 ideas라는 배열 안에 없어야한다.

물론 단어의 순서에 따라 이름이 달라지니까 그러한 것도 고려해야하며 가능한 서로 다른 이름의 개수를 구하는 문제였다.

 

ex) ideas = ["coffee", "donuts", "toffee"]가 있다고 가정하자 이를 통해 가능한 경우와 불가능한 경우를 생각해보면

- ("coffee", "donuts") = "doffee conuts" (각각의 단어가 ideas에 없으므로 가능)

- ("coffee", "toffee") = "toffee doffee" (각각의 단어가 ideas에 존재하므로 불가능)

 

 

문제 해결 흐름

1. 처음에 보고 이렇게 쉬운 문제가 왜 Hard?라며 간단하게 for문을 써서 해결해보고자 했다. (Naive한 방법)

→  두 단어씩 비교하며 앞단어를 바꿨을 때 해당 배열에 있는지 확인

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        ans = 0;

        for i in range(0, len(ideas)-1):
            for j in range(i + 1, len(ideas)):
                first = ideas[i];
                last = ideas[j];

                if first[0] != last[0]:
                    if (first[0] + last[1:]) not in ideas:
                        if (last[0] + first[1:]) not in ideas:
                            ans += 2;

        return ans;

그 결과 TLE(Time Limit Exceeded)가 나왔다.

=> 매우 비효율적인 방법이었다. ideas의 크기는 자그만치 50000으로 time Complexity가 O(N^2) ~ O(N^4)이다.

 

Time Complexity: O(N^2) ~ O(N^4)

우선 2중 for문을 사용하고 있으니까 O(N^2)에 내부  if문에서 서로 첫 문자를 바꿨을 때 ideas에 있는지 확인하는 것 또한 for문이기 때문에 O(N^4)까지 될 것이다.

 

Space Complexity: O(1)

ans외에 기존에 주어진 배열내에서 in-place로 진행했기 때문에 O(1)의 공간복잡도를 가진다. 

 

 

다른 해결 방식

1. '찾는' 문제이므로 외부 for문이 돌아가는 것은 어쩔 수 없고 뭔가 중복에 대한 처리가 필요하겠다.

→ 우선 문제에서 맨 앞 단어를 서로 바꾼다고 했으니까 앞단어와 뒷단어를 따로 떼서 생각해봐야겠다.

ideas = ["cat","coffee","donuts","time","toffee", "cpa", "truck"]

"c": ["at", "offee", "pa"]
"d": ["onuts"]
"t": ["ime","offee", "ruck"]

일단 불가능한 조건을 생각해본다면

 

1) 같은 앞단어를 가지고 있는 경우    

ex) "time"과 "toffee"의 경우 앞단어를 서로 바꾸면 자기 자신이 되므로 안된다.

 

2) 다른 앞단어라도 뒷단어가 같은 경우

ex) "coffee"와 "toffee"의 경우 앞단어를 서로 바꾸면 결국엔 같은 단어로 안된다.

 

3) 앞단어와 뒷단어가 서로 다르더라도 불가능한 경우

ex) "coffee"와 "truck"의 경우 앞단어를 서로 바꾸면 "toffee"가 나오게 되므로 안된다.

 

→ 중복된 부분을 빼고 경우의 수를 구해보면 좋을 것 같다. 우선 2개씩 결합하므로 2개씩 벤다이어그램을 그리자.

 

우선 c와 t로 시작하는 집합의 벤다이어그램을 그려보면 이렇게 그려질 것이다.

위의 패턴을 확인한다면 둘 사이의 교집합인 부분을 제외하고 경우의 수를 구한다면 해결이 된다는 것을 확인가능하다.

즉 교집합 부분을 제외한 ["at","pa"]와 ["ime","ruck"]의 조합인 2*2의 경우의 수가 나오게 된다.

 

이 아이디어를 코드로 옮기면

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        ans = 0;

        fDict = dict();	                             // 앞단어를 key 뒷단어를 value로 담기
        fArr = []                                    // 앞단어를 담을 배열

        for word in ideas:
            fword = word[0];		
            lword = word[1:] if len(word) > 1 else ' '; // 한자리 인 경우 ' '으로 담음
            
            if fword not in fArr:                    // 앞단어가 없으면 fArr에 담음
                fArr.append(fword);
                
            if fword not in fDict:                   // dict에 key value쌍으로 저장
                fDict[fword] = {lword};
            else:
                fDict[fword].add(lword);
        
        for i in range(len(fArr) - 1):
            for j in range(i+1, len(fArr)):          // 각각의 차집합된 원소의 수를 곱하면 경우의 수 도출
                case = len(fDict[fArr[i]] - fDict[fArr[j]]) * len(fDict[fArr[j]] - fDict[fArr[i]]);
                ans += (case*2);                     // 앞뒤 자리 바꿀 수 있으니까 *2

        return ans;

=> 집합개념과 경우의 수 개념을 이용하여 굳이 확인하지 않고 수치적으로 해결한 방법

 

 

Time Complexity: O(N) ~ O(N^2)

딕셔너리에 값을 넣기 위해 돌린 for문정도가 Time Complexity에 크게 영향을 줄 것이기에 O(N)일 것이다. 물론 fDict의 크기가 26이고 앞단어가 a-z까지라면 아래있는 2중 for문이 26*(25!)번 돌것이기 때문에 이 경우  O(N^2)도 될 수 있겠다.

 

Space Complexity: O(N)

fDict이라던지 fArr을 사용했기 때문에 O(N)의 공간복잡도를 가질 것이다.

 

문제 링크

https://leetcode.com/problems/naming-a-company/description/

Naming a Company - LeetCode