LeetCode[ 383 | Python ] Ransom Note

문제

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

ransomNote 와 magazine 두 문자열이 주어졌을 때 ransomNote가 magazine에 있는 철자들을 통해 구성될 수 있을지 true, false를 반환해야하는 문제.

풀이

시도

실행 시간 : 39ms
메모리 : 13.4MB

1. magazine 에 있는 모든 철자를 해시테이블 dic에 저장한다.
   1. 이 때 개수를 고려해야 하므로 이미 철자가 존재하면 합산한다.
2. ransomNote를 순회하며 철자가 dic에 존재하는 경우 dic에 있는 값을 감소시킨다.
   1. dic을 통해 찾은 원소의 값이 0 미만이거나 존재하지 않으면 False를 반환한다.
3. 정상적으로 코드가 수행되었으면 True를 반환한다.

HashTable을 이용해서 풀 수 있는 기초적인 문제였다.
딕셔너리를 이용한 Counting을 수행해 준수한 실행시간과 메모리를 이용해 해결할 수 있었다.

class Solution(object):
    def canConstruct(self, ransomNote, magazine):
        dic = {}
        for m in magazine:
            if not m in dic:
                dic[m] = 1
            else:
                dic[m] += 1

        for r in ransomNote:
            if r in dic:
                if dic[r] <= 0:
                    return False
                else:
                    dic[r] -= 1
            else:
                return False
        return True