383. Ransom Note

🚥 문제 🚥

Top Interview 150 중 383. Ransom Note

🍿 난이도 : 리트코드 기준 Easy
🚧 알고리즘 : hash table

🚦 풀이1 🚦

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        for alpha in ransomNote:
            if alpha in magazine:
                i = magazine.find(alpha)
                magazine = magazine[:i] + magazine[i+1:]
            else:
                return False
        return True

🚧 우선 생각나는대로, ransomnote에 있는 알파벳이 magazine에 있는지 확인했다.

🚧 만약 있는 알파벳이라면 magazine을 해당 알파벳을 뺀 값으로 변경했고, 없는 알파벳이라면 바로 false를 돌려줬다.

풀이 결과

나름 괜찮은 런타임과 메모리사용량을 보여줬고, 바로 풀었기 때문에 나쁘지 않았지만, 이 문제가 해쉬를 이용하는 문제로 출제되었음을 알고 있었기 때문에, 다시 풀어야겠다고 생각했다.

🚦 풀이2 🚦

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        notecnt = Counter(ransomNote)
        magcnt = Counter(magazine)
        for i in notecnt :
            if (magcnt[i] < notecnt[i]):
                return False
        return True

🚧 다른 사람이 풀어낸 문제를 풀어내면 좋은 순서를 읽다가, Counter를 이용할 수 있다는 것을 알았다.

🚧 두 string을 각각 counter객체로 만들어줬다.

"a"   => Counter({'a': 1})
"aab" => Counter({'a': 2},{'b': 1})

🚧 notecnt에 있는 하나의 dict마다, 동일한 키값을 갖고 있는 dict를 magcnt에서 찾아서, value값을 비교해줬다. value값이 notecnt의 value값보다 작으면, 사용할 수 있는 알파벳이 충분하지 않다는 의미이므로 false를 리턴했다.

풀이 결과

런타임 속도가 조금 느려졌지만, 메모리 사용량이 줄어들었다.
📌 hash를 위해서 counter객체를 사용한다는 사실을 알게되었다.

타인의 코드

notecnt = Counter(ransomNote)
magcnt = Counter(magazine)
return (notecnt & magcnt == notecnt)

Counter() 함수는 collections module에 포함되어있다.
카운터 객체의 사용방법을 더 다양하게 알게되었다.
counter객체 & counter객체를 하면, 결과값은 counter객체인데, dict의 값에 key는 동일하고, value중에서 중복값만 저장된다.
& 연산이 조금 시간이 오래걸리겠지만, 코드가 간결해지고, 의미가 바로 전달된다는 점에서 좋다고 생각했다.

추가적으로, counter객체에 저장할 수 있는 예제를 공부해보자