Week 2-1. [Hash Table] 383. Ransom Note (Python3)

문제 해결 과정

✍️ 나만의 방식으로 문제 정리하기 (=체계화)

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

Ransom Note - LeetCode

ransomNote와 magazine 두 개의 문자열이 주어질 때,
magazine의 철자들을 이용해 ransomNote를 구성할 수 있다면 True, 없다면 False를 반환하라.

• | ransomNote, magazine | ∈ [1, 10^5]
• ransomNote와 magazine은 알파벳 소문자만으로 이루어져 있다.

 

🔎 어떤 식으로 접근했는가?

예를 들어 magazine="aab"이고 ransomNote="aa"라면 magazine의 철자로 ransomNote를 구성할 수 있으니 True를 반환한다.

 

예시를 보자마자 딕셔너리가 생각났다.

magazine을 순회하며 딕셔너리에 알파벳과 빈도수를 누적하고, 이어서 ransomNote를 순회하며 같은 딕셔너리에서 빈도수를 차감한다.

 

ransomNote를 다 순회했을 때, 딕셔너리에 양수 혹은 0은 있어도 되지만 음수가 있으면 안된다.

(딕셔너리 values에 음수가 있다면, ransomNote에는 있는 알파벳이 magazine에는 없었다는 의미이다.)

 

🙈 알고리즘 선택: 입력의 크기를 바탕으로

ransomNote와 magazine의 최대 길이가 10^5이므로 linear search를 이용한다.

 

📝 의사 코드

magazine을 순회하며:
	딕셔너리에 각 원소의 빈도수를 누적한다.
    
ransomNote를 순회하며:
	딕셔너리에서 각 원소의 빈도수를 차감한다.
    
딕셔너리의 values가 모두 양수이면: return True
아니면: return False

 

🎯 구현 코드

from collections import defaultdict

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:

        dic = defaultdict(int)
        for x in magazine:
            dic[x] += 1

        for x in ransomNote:
            dic[x] -= 1

        if all(x >= 0 for x in dic.values()): return True
        else: return False

 

내 코드를 탐구해보기

⏱ 성능 측정 (시간복잡도/공간복잡도)

linear search로 시간복잡도는 O(n)이다.

 

✍️ 성능 회고

1초 제한에서 O(n)의 최대 입력은 10^6이다. 문제에서는 최대 입력이 10^5이므로 성능은 괜찮다.

 

다른 사람의 코드를 탐구해보기

🎯 구현 코드

Counter 함수를 이용해 문자열의 빈도수를 카운트 한다.

논리 AND는 교집합을 의미한다.

st1과 st2의 AND 결과가 st1 이라면 magazine과 ransomNote의 교집합이 ransomNote라는 것이다.

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:

        st1, st2 = Counter(ransomNote), Counter(magazine) # 각 문자열 빈도수 카운트
        return st1 & st2 == st1 # 논리 AND의 결과가 st1이라면 True

 

⏱ 성능 측정 (시간복잡도/공간복잡도)

Counter 함수를 호출했을 때 각 문자열의 길이만큼 문자를 순회한다. 따라서 시간 복잡도는 O(n)이다.

 

느낀 점

논리 연산자를 활용해본 경험이 많이 없는데, 이런 경우에 활용할 수 있음을 깨달았다.