Hash Tables: Ransom Note

기초적인 hash table 문제로 단순한 조회와 리스트 내의 아이템들의 수를 관리하는게 결합된 형태이다.

Problem

Harold is a kidnapper who wrote a ransom note, but now he is worried it will be traced back to him through his handwriting. He found a magazine and wants to know if he can cut out whole words from it and use them to create an untraceable replica of his ransom note. The words in his note are case-sensitive and he must use only whole words available in the magazine. He cannot use substrings or concatenation to create the words he needs.

Given the words in the magazine and the words in the ransom note, print Yes if he can replicate his ransom note exactly using whole words from the magazine; otherwise, print No.

문제에 사족이 많지만 function description을 보면 결국 note에 있는 단어가 magazine에 있는지 확인하면되는 간단한 문제이다. 다만 note에 두 번 등장한 단어가 있는데 magazine에 해당 단어가 한 개 밖에 없다면 No를 띄워야 한다는 것만 주의하면 된다.

Answer

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from collections import Counter

def checkMagazine(magazine, note):
    ref = Counter(magazine)
    for i in note:
        if (i not in ref) or (ref[i] == 0):
            print("No")
            return
        ref[i] -= 1
    print("Yes")
    return

Explanation

Python의 built-in Counter를 활용하면 단어별로 수를 세는 부분을 깔끔하게 처리할 수 있다. collections에서는 실무적으로 유용하게 사용할 수 있는 클래스들이 많이 있으므로 한번쯤 눈여겨보는 것도 좋을 것이다. 이후는 key값 유무 확인 및 사용할 수 있는 단어 수를 확인하는 것으로 간단하게 구현할 수 있다.

Reference

• HackerRank