LeetCode [383]: Ransom Note

📌 LeetCode [383]: Ransom Note

🔗 문제 링크

---

문제 설명 📄

주어진 문자열 ransomNote가 문자열 magazine의 문자들만으로 구성될 수 있는지 확인하는 문제입니다.

• 각 문자는 magazine에서 하나씩만 사용할 수 있습니다.

---

문제 해결 접근 📋

1. collections.Counter를 사용하여 두 문자열의 문자의 개수를 세어 각각의 빈도수를 저장합니다.
2. & 연산자를 사용하여 두 카운터의 교집합을 구하고, 이 교집합이 ransomNote의 카운터와 동일한지 비교합니다.
3. 동일하다면 True를 반환하고, 그렇지 않다면 False를 반환합니다.

---

Solution 💻

from collections import Counter

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        st1, st2 = Counter(ransomNote), Counter(magazine)
        if st1 & st2 == st1:
            return True
        return False

시간 복잡도 ⏲️

• 시간 복잡도: O(n + m)
  • n은 ransomNote의 길이, m은 magazine의 길이입니다.
  • Counter를 통해 각 문자열의 문자의 빈도를 계산하는 데 걸리는 시간입니다.

공간 복잡도 🗄️

• 공간 복잡도: O(n + m)
  • 두 문자열의 카운터를 저장하기 위한 공간입니다.

---

리팩토링 🛠️

개선된 코드

from collections import Counter

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        st2 = Counter(magazine)
        for char in ransomNote:
            if st2[char] <= 0:
                return False
            st2[char] -= 1
        return True

리팩토링 후 시간 복잡도 ⏲️

• 시간 복잡도: O(n + m)
  • n은 magazine의 길이, m은 ransomNote의 길이입니다.
  • Counter 생성과 ransomNote를 순회하는 데 걸리는 시간입니다.

리팩토링 후 공간 복잡도 🗄️

• 공간 복잡도: O(m)
  • magazine의 카운터만 사용하므로 공간 사용량이 더 적습니다.

---