LeetCode 383(Ransom Note, Python)

1. 문제 링크

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

Ransom Note - LeetCode

2. 문제 설명

• 두 문자열 ransomNote, magazine이 주어졌을 때 magazine의 문자열을 이용하여 ransomNote를 만들어낼 수 있는 지 True, False 반환하는 문제
• 문자열의 순서는 자유롭게 바꿀 수 있으며 magazine에 문자열은 한 번씩 사용 가능하다. a가 두 개 있으면 두 번까지, 하나 있으면 한 번만 사용할 수 있음.
• 예시1) ransomNote = "a", magazine = "b" 이면 False
• 예시2) ransomNote = "aa", magazine = "ab"이면 False
• 예시3) ransomNote = "aa", magazine = "aab"이면 True

3. 처음 풀이

• ransomNote와 magazine의 각 문자의 등장 횟수를 세기 위해 딕셔너리 check1과 check2 생성
• ransomNote의 각 문자를 순회하면서 해당 문자의 등장 횟수를 check1에 기록
• magazine의 각 문자를 순회하면서 해당 문자의 등장 횟수를 check2에 기록
• check1에 등장한 각 문자와 그 등장 횟수를 순회하면서 해당 문자가 check2에도 있고, 그 등장 횟수가 충분하면 계속 진행하고, 아니라면 False를 반환. 모든 문자에 대해 확인이 끝나면 True를 반환

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        check1 = {}  # ransomNote의 각 문자의 등장 횟수를 저장하기 위한 딕셔너리
        check2 = {}  # magazine의 각 문자의 등장 횟수를 저장하기 위한 딕셔너리

        # ransomNote의 각 문자의 등장 횟수를 계산하여 check1에 저장
        for s in ransomNote:
            if s in check1:
                check1[s] = check1[s] + 1
            else:
                check1[s] = 1

        # magazine의 각 문자의 등장 횟수를 계산하여 check2에 저장
        for s in magazine:
            if s in check2:
                check2[s] = check2[s] + 1
            else:
                check2[s] = 1
        
        # ransomNote의 각 문자와 그 등장 횟수를 magazine에서 확인
        for key in check1:
            if key not in check2:  # magazine에 해당 문자가 없으면 조건 불만족
                return False
            elif check1[key] > check2[key]:  # magazine에 해당 문자의 등장 횟수가 부족하면 조건 불만족
                return False
        
        return True  # 모든 조건을 만족하면 ransomNote를 만들 수 있음

4. 다른 풀이

• ransomNote의 각 문자를 magazine에서 찾아 제거하는 방식으로 접근. replace 메서드를 사용하여 문자를 찾아 제거. magazine에 해당 문자가 없으면 False
• replace를 할 때 문자열이 새로 생겨나서 공간 복잡도 측면에서 효율적이지 못함.

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        for c in ransomNote:
            if c in magazine:
                magazine = magazine.replace(c, '', 1)
            else:
                return False
        return True

---

• collections 모듈의 Counter 클래스를 사용하여 ransomNote의 각 문자의 등장 횟수와 magazine에서 해당 문자의 등장 횟수를 비교하여 충분한 지 확인.

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        # ransomNote에서 중복을 제거한 문자 집합 생성
        unique_characters = set(ransomNote) 

        # 각 문자에 대해 magazine과 ransomNote에서의 등장 횟수 비교
        for char in unique_characters:
            if magazine.count(char) < ransomNote.count(char):
                # ransomNote에서의 등장 횟수가 더 많으면 False 반환하고 반복 종료
                return False
                break
        
        # 모든 문자에 대해 등장 횟수가 충분하면 True 반환
        return True

5. 배운 점

• Counter 라이브러리를 적극적으로 활용하자.
  • **Counter**는 Python의 내장 모듈인 **collections**에 포함된 클래스로, 주어진 순회 가능한(iterable) 객체의 각 요소의 개수를 셈. 주로 리스트, 튜플, 문자열 등과 같은 iterable한 데이터에 대해 각 요소의 빈도를 계산하는 데 사용
  • 사용 예시

  from collections import Counter
  
  # 리스트에서 각 요소의 개수 세기
  my_list = [1, 2, 3, 1, 2, 1, 4, 5, 4]
  counter_list = Counter(my_list)
  print(counter_list)
  # 출력: Counter({1: 3, 2: 2, 4: 2, 3: 1, 5: 1})
  
  # 문자열에서 각 문자의 개수 세기
  my_string = "hello"
  counter_string = Counter(my_string)
  print(counter_string)
  # 출력: Counter({'l': 2, 'h': 1, 'e': 1, 'o': 1})