[알고리즘/Python] 383. Ransom Note

📑 1. 문제 이해

https://leetcode.com/problems/ransom-note/?envType=study-plan-v2&envId=top-interview-150 

Ransom Note - LeetCode

이 문제는 magazine의 문자들을 활용해서 ransomNote를 작성할 수 있는지 확인하는 문제입니다.  ransomNote란 다음 그림처럼 잡지에 등장하는 글자를 하나씩 잘른 후 합쳐서 원하는 문자를 만드는 것을 말합니다.

 

- 문자열은 빈 문자열일 수 없으면 영문자 소문자만 포함한다.

☑️ 테스트케이스

문제에서 주어진 테스트케이스는 다음과 같습니다.

 

Example1: ransomNote = "a", magazine = "b"

- ransomNote의 문자가 magazine에 존재하지 않는다.

 

Example2: ransomNote = "aa", magazine = "ab"

- ransomNote의 문자가 magazine에 존재하지만 갯수가 모자란다.

 

Example3: ransomNote = "aa", magazine = "aab"

- ransomNote의 문자가 magazine에 모두 존재하며 magazine의 문자가 더 많습니다.

 

💡 2. 알고리즘 설계

딕셔너리를 활용해서 문자 구성을 비교할 수 있습니다. 이때  원소별 개수를 세기 위해서는 딕셔너리를 확장한 Counter를 사용하면 편리합니다. magazine의 문자 구성을 딕셔너리에 {문자: 카운트}형태로 저장한 후 ransomeNote의 각 문자들을 magazine에서 존재하는지 확인합니다. 이미 사용한 문자는 카운트를 -1해서 더 이상 사용되지 못하도록 합니다.

 

1. 만약 ransomNote의 길이가 magazine의 길이보다 더 길다면 무조건 False를 반환합니다.

2. Counter를 사용하여 magazine의 문자별 갯수를 셉니다.

3. ransomeNote의 각 문자에 대해서 카운터를 확인합니다. 만약 존재하지 않거나 그 개수가 0과 같다면 원하는 문자가 magazine에 존재하지 않는다는 것으로 False를 반환합니다.

4. 이미 사용한 문자는 제외시키기 위해 카운트를 1 감소 시킵니다.

5. ransomNote의 모든 문자에 대해 비교가 끝났다면 True를 반환합니다.

    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        if len(ransomNote) > len(magazine):
            return False

        chars = Counter(magazine)

        for c in ransomNote:
            if c not in chars or chars[c] <= 0:
                return False
            chars[c] -= 1
        return True

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 두 문자열을 각각 한번씩 순회해야합니다. Counter를 만들기 위해서도 내부적으로 문자열을 순회하며 딕셔너리에 저장합니다. 

공간 복잡도: O(N). 한 개의 카운터가 저장될 공간이 필요합니다. 최악의 경우 모든 문자가 달라 딕셔너리의 키 개수가 배열의 길이와 같습니다.

 

⚒️ 3. 최적화

 직접 비교하지 않고 Counter가 제공하는 교집합 연산을 사용할 수 있습니다. ransomNote가 magazine에 포함된다면 두개의 교집합이 ransomNote이고, 두개의 합집합이 magazine이 됩니다. 이때 교집합을 찾는 것이 어느정도 연산속도를 더 높일 수 있습니다. 합집합의 경우 두 counter를 key값이 더 많은 counter를 기준으로 하지만, 교집합의 경우 두 counter 중 key값이 더 작은 counter를 기준으로 비교하기 때문입니다.  실제 python의 Counter 클래스의 소스코드를 보면 다음과 같습니다.

 class Counter(dict):
	 def __or__(self, other):
        '''Union is the maximum of value in either of the input counters.
        >>> Counter('abbb') | Counter('bcc')
        Counter({'b': 3, 'c': 2, 'a': 1})
        '''
        if not isinstance(other, Counter):
            return NotImplemented
        _max = max
        result = Counter()
        for elem in set(self) | set(other):
            newcount = _max(self[elem], other[elem])
            if newcount > 0:
                result[elem] = newcount
        return result

    def __and__(self, other):
        ''' Intersection is the minimum of corresponding counts.
        >>> Counter('abbb') & Counter('bcc')
        Counter({'b': 1})
        '''
        if not isinstance(other, Counter):
            return NotImplemented
        _min = min
        result = Counter()
        if len(self) < len(other):
            self, other = other, self
        for elem in ifilter(self.__contains__, other):
            newcount = _min(self[elem], other[elem])
            if newcount > 0:
                result[elem] = newcount
        return result

 또한 ransomNote의 길이가 magazine의 길이보다 더 긴 경우 False를 반환해 불필요한 비교를 수행하지 않을 수 있습니다. 전체 소스코드는 다음과  같습니다.

    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        if len(ransomNote) > len(magazine):
            return False

        magazineChars = Counter(magazine)
        ransomNoteChars = Counter(ransomNote)

        return magazineChars & ransomNoteChars == ransomNoteChars

이때 counter 사이에 비교하기 위해 사용되는 == 연산은 참조값을 비교하는 것이 아니라 실제 값을 비교한다.

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). Counter를 만들기 위해서도 내부적으로 문자열을 순회하며 딕셔너리에 저장합니다. 

공간 복잡도: O(N). 두개의 카운터가 저장될 공간이 필요합니다. 최악의 경우 모든 문자가 달라 딕셔너리의 키 개수가 배열의 길이와 같습니다.

 ⎌ 4. 검토

Example1: ransomNote = "a", magazine = "b"

- 두 counter의 교집합이 None이 되어 False가 반환됩니다.

 

Example2: ransomNote = "aa", magazine = "ab"

-두 counter의 교집합이 {a:1}이 되어 ransomNote 카운터 {a:2}와 다르므로 `magazineChars & ransomNoteChars == ransomNoteChars` 가 Fasle가 됩니다.

 

Example3: ransomNote = "aa", magazine = "aab"

- magazine의 길이가 더 길기때문에 길이 비교ㅛ에서 False가 반환되지 않습니다. 두 counter의 교집합이 ransomNote 카운터와 같으므로 True가 반환됩니다.

---

✅ 정리

◎ Counter는 합집합, 교집합, 차집합의 연산을 제공합니다. 

◎  python은 list, dictionary 등 collection 타입을 == 연산으로 비교하는 경우 참조값이 아니라, 그 실제 값을 비교합니다.