3 분 소요

Hash Table

문제

문제 링크

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

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 <= 105
  • ransomNote and magazine consist of lowercase English letters.

스스로 고민

접근법

  • 두 개의 문자열이 주어진다
  • magazine 문자열로 ransomNote 글을 만들 수 있으면 true 아니면 false
  • magazine 에서 문자는 각 한 번씩만 사용할 수 있다.

의사코드

  • magazine_list 와 ransomNote_list 가각 리스트를 선언해준다.
  • 각각 문자열을 리스트로 만들어준다.
  • 해당 리스트에 해당 문자가 있다면 해당 문자를 제거해준다
  • 모든 반복문이 끝난 후 ransomNote_list에 남아있는게 없다면 magazine 문자로 전부 사용된거니 True 아니라면 False

구현 코드

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        magazine_list = []
        ransomNote_list = []

        for letter in magazine:
            magazine_list.append(letter)

        for letter in ransomNote:
            ransomNote_list.append(letter)

        for letter in magazine_list:
            if letter in ransomNote_list:
                ransomNote_list.remove(letter)
        if len(ransomNote_list) == 0:
            return True
        else:
            return False

시간 복잡도와 공간 복잡도

시간 복잡도:

  • 첫 번째 반복문에서 magazine의 각 문자를 magazine_list에 추가하는데, 이는 magazine의 길이에 비례하는 작업이다. 따라서 이 부분의 시간 복잡도는 O(n) 다.
  • 두 번째 반복문도 마찬가지로 ransomNote의 길이에 비례하는 작업을 수행하므로 시간 복잡도는 O(m) 다. 여기서 m은 ransomNote의 길이다.
  • 세 번째 반복문에서 magazine_list의 각 문자를 순회하고, ransomNote_list에서 해당 문자를 제거하는데, 이 과정에서 remove() 메서드를 사용하면 ransomNote_list의 길이가 변경된다. remove() 메서드의 시간 복잡도는 최악의 경우 O(n) 다. 따라서 이 부분의 시간 복잡도도 최악의 경우 O(n)이 될 수 있다.
  • 따라서 전체적으로 canConstruct() 메서드의 시간 복잡도는 O(n + m + n)으로 표현할 수 있다. 여기서 n은 magazine의 길이, m은 ransomNote의 길이다.

공간 복잡도:

  • magazine_list와 ransomNote_list라는 각 리스트는 최대 magazine와 ransomNote의 길이만큼의 공간을 사용하므로, 공간 복잡도는 O(n + m)다.
  • 나머지 변수들은 상수 개수의 메모리를 사용하므로 공간 복잡도에 큰 영향을 미치지 않는다.
  • 따라서 전체적으로 공간 복잡도는 O(n + m) 다.

회고 과정

지금 코드에서 뭘 개선할 수 있지?

리스트를 사용하여 중복된 문자를 처리하고 있는데 결과 값의 성능이 좋지 않았다. 해시맵을 통해서 해결할 수 있는 방법을 생각해봤는데 잘 생각나지 않아서 해시맵을 사용해서 해결한 방법을 찾아봤다.

from collections import defaultdict

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        magazine_map = defaultdict(int)

        # Fill the magazine_map with character frequencies
        for char in magazine:
            magazine_map[char] += 1
        
        # Check if ransomNote can be constructed
        for char in ransomNote:
            if char not in magazine_map or magazine_map[char] == 0:
                return False
            magazine_map[char] -= 1
        
        return True
  • defaultdict 를 사용해서 해시맵을 구현해서 해결할 수 있다.
  • defaultdict 는 내장 클래스로서 딕셔너리를 생성하는데 사용할 수 있다.
from collections import defaultdict

# defaultdict 생성
my_dict = defaultdict(int)  # int의 기본값인 0으로 초기화

# 값을 추가
my_dict['a'] = 1
my_dict['b'] = 2

# 기본값 확인
print(my_dict['c'])  # 출력: 0

# 기본값의 데이터 타입 변경
my_dict = defaultdict(list)  # 리스트로 초기화

# 값을 추가
my_dict['x'].append(10)
my_dict['y'].append(20)

# 기본값 확인
print(my_dict['z'])  # 출력: []

defaultdict를 생성할 때, 생성자로 기본값의 타입을 지정해주어야 한다. 예를 들어 int, list, set 등이 기본값으로 사용될 수 있다. 생성한 defaultdict를 일반적인 딕셔너리처럼 사용하면 되며, 존재하지 않는 키에 접근하면 해당 기본값이 반환된다.

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

class Solution:
    def canConstruct(self, RN: str, M: str) -> bool:
        for i in RN:
            if i in M:
                M = M.replace(i,"",1)
            else: return False
        return True
  • replace 함수만으로 간단하게 문제를 해결한 경우다.
  • 반복문을 통해 해당 글자가 있다면 replace를 통해 일치하는 문자중 가장 첫 번째 문자를 삭제하고 반복문이 끝날 때까지 이상이 없다면 자동으로 True를 반환
  • magazine 안에 문자가 모자를 경우 false를 반환하게 만든다.
  • replace를 잘 활용할 수 있게 떠올랐다면 지금 문제를 해결할 때 정말 편했을 거 같다.

댓글남기기

참고