[리트코드] 383. Ransom Note

문제

https://leetcode.com/problems/ransom-note/

Example 1:

Input: ransomNote = "a", magazine = "b"
Output: false

Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false

Example 3:

Input: ransomNote = "aa", magazine = "aab"
Output: true

Constraints:

• 1 <= ransomNote.length, magazine.length <= 10**5
• ransomNote and magazine consist of lowercase English letters.

---

✔ 문제접근 #1 해시[통과] ⭕

Intuition
magazine요소들의 등장횟수를 카운트하여 dict자료구조에 저장한다. ransomNote의 요소를 하나씩 매칭하고 지워하면서 문제를 해결한다.

Algorithm
dict 자료구조 h를 선언하고 magazine의 각각의 요소 개수를 카운트하여 저장한다.

ransomNote의 요소가 등장할 때마다 h에서 각요소의 개수를 -- 해준다. 만약 해당 요소가 없거나, 더이상 매칭할 수 없다면(h[elem] == 0) False를 반환한다.

    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        
        h = dict()
        
        # magazine의 각각 요소의 개수를 구해준다.
        for elem in magazine:
            if elem in h:
                h[elem] += 1
            else:
                h[elem] = 1
                
                
        # ransomNote의 각 요소를 h에서 하나씩 지워준다.
        for elem in ransomNote:
            # ransomeNote의 해당 요소가 magazine에 없다면 실패
            if elem not in h:
                return False
            
            # 더이상 사용할 수 있는(매칭되는) 요소가 없다면 실패
            if h[elem] == 0:
                return False
            
            h[elem] -= 1
            
            
        return True

 

Complexity Analysis

• 시간 복잡도 : O(N + M)
  • magazine의 각 요소개수 카운트O(N)
  • ransomNote 요소를 순회 O(M)
  • 그러므로 전체시작복잡도 : O(N + M)

• 공간복잡도 : O(N)
  
  • dict 자료구조를 사용한다.

---

기타풀이 및 회고

python에서 코드를 조금 더 간결하게 사용하고 싶다면 dict보다는 default dict를 활용하여 기본값을 0으로 두고 사용하는 것이 좋다. 도움이 되는 도구가 있다면 구현하지말고 활용하자.