[코딩 인터뷰] LeetCode - 383. Ransom Note 파이썬 해시 테이블과 카운터 사용법

👋 안녕하세요👨‍💻 이번에 다룰 문제는 LeetCode의 '383. Ransom Note'라는 문제인데요, 문자열 처리 능력을 시험하는 정말 흥미진진한 문제랍니다! 🕵️‍♂️💻

 

 

릿코드. LeetCode - 383. Ransom Note

 

---

문제 설명 🧐

문제의 핵심은 다음과 같아요. 두 문자열, ransomNote와 magazine이 주어질 때, ransomNote가 magazine의 문자들을 사용해서 만들어질 수 있는지 판단하는 거예요. 단, magazine의 각 문자는 한 번씩만 사용할 수 있습니다.

예를 들어보죠! 🌟

• 예시 1: ransomNote = "a", magazine = "b" ➡️ 결과: false
• 예시 2: ransomNote = "aa", magazine = "ab" ➡️ 결과: false
• 예시 3: ransomNote = "aa", magazine = "aab" ➡️ 결과: true

문제 보기 - LeetCode - 383. Ransom Note 

---

알아야 할 개념 공부하기 📚

 

• 해시 테이블 - 키와 값을 저장하는 자료 구조입니다. 키는 중복될 수 없고, 값은 중복될 수 있습니다.
• 슬라이딩 윈도우 - 특정 범위의 데이터를 윈도우라고 보고, 윈도우를 이동하면서 데이터를 처리하는 기법입니다.

---

문제 풀어보기 ✍️

이제 문제를 풀어볼 시간이에요! 먼저, magazine 문자열을 순회하면서 해시 테이블에 문자의 빈도수를 기록합니다. 그 다음, ransomNote를 순회하면서 해시 테이블에 기록된 magazine의 문자 빈도수를 차감해가며, ransomNote를 만들 수 있는지 확인합니다. 만약 ransomNote의 문자가 해시 테이블에 없거나 빈도수가 0이면, false를 반환하죠. 🚀🔍

def canConstructRansomNote(ransomNote, magazine):
    # Create a dictionary to store the frequency of each character in magazine
    char_frequency = {}
    for char in magazine:
        char_frequency[char] = char_frequency.get(char, 0) + 1

    # Check each character in ransomNote
    for char in ransomNote:
        if char_frequency.get(char, 0) == 0:
            return False  # If the character is not in magazine or frequency is 0
        char_frequency[char] -= 1  # Decrement the frequency

    return True  # All characters are found in magazine

# Test the function with the provided examples
example1 = canConstructRansomNote("a", "b")
example2 = canConstructRansomNote("aa", "ab")
example3 = canConstructRansomNote("aa", "aab")

(example1, example2, example3)

 

Counter를 이용해서 문제풀기 

from collections import Counter
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
    ransome_counter = Counter(ransomNote)
    magazine_counter = Counter(magazine)
    return (ransome_counter - magazine_counter) == {}

 

1. Counter 객체 생성하기 Counter 클래스는 iterable한 객체(여기서는 문자열)를 입력으로 받아, 그 안의 각 요소(문자)의 빈도수를 계산합니다. 예를 들어, Counter("aab")는 {'a': 2, 'b': 1}의 형태로 반환합니다.
2. ransomNote와 magazine의 빈도수 계산하기 ransomNote와 magazine 문자열에 대해 각각 Counter 객체를 생성합니다. 이렇게 해서 각 문자열에 포함된 문자들의 빈도수가 계산됩니다.
3. 두 Counter 객체 간의 차이 계산하기 ransomNote의 Counter 객체에서 magazine의 Counter 객체를 빼면, ransomNote에만 있는 문자들의 빈도수가 나타납니다. 예를 들어, Counter("aa") - Counter("aab")는 빈 딕셔너리 {}를 반환합니다. 이는 magazine 문자열이 ransomNote 문자열의 모든 문자를 포함하고 있음을 의미합니다.
4. 결과 반환하기 ransomNote에서 magazine을 뺀 결과가 빈 딕셔너리 {}이면, ransomNote를 magazine의 문자들로 구성할 수 있다는 뜻입니다. 따라서 이 경우 True를 반환합니다. 만약 결과가 빈 딕셔너리가 아니라면, False를 반환합니다.

 

이 방법은 Counter 클래스의 강력한 기능을 활용하여 문제를 매우 효율적으로 해결할 수 있게 해줍니다. 코드가 간결하고 이해하기 쉬우며, 빈도수 계산과 비교를 단순화합니다.

---

🎯 이 문제를 통해 문자열 처리와 해시 테이블의 개념을 더 깊이 이해할 수 있었어요. 코딩 문제를 풀면서 이렇게 새로운 개념을 배우고 익히는 과정은 정말 즐겁고 보람찬 일이죠! 여러분도 이 문제를 통해 코딩 실력을 한 단계 업그레이드 시켜보세요! 💪🧑‍💻 Happy Coding! 👩‍💻