[해시 테이블] 29 보석과 돌(Jewels and Stones)

<LeetCode 문제>

https://leetcode.com/problems/jewels-and-stones/

Jewels and Stones - LeetCode

jewels는 보석이고, stones는 갖고 있는 돌일때, stones에는 보석이 몇 개나 있을지 구하는 문제입니다. 이때 대소문자는 구분합니다.

<풀이>

파이썬의 collections.Counter를 이용하여 한 첫번째 풀이는 다음과 같습니다.

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        counter_stones = Counter(stones) #시간복잡도 O(n)
        
        ans=0
        for now_j in jewels:
            ans+=counter_stones.get(now_j,0)
        return ans

 

이때, collections.Counter의 반환값으로 Counter객체가 반환되는데 Counter객체는 defaultdict과 마찬가지로 존재하지 않는 키에 대해 0을 반환해줍니다. 따라서 get함수를 이용하지 않아도 됩니다.

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        counter_stones = Counter(stones) #시간복잡도 O(n)
        
        ans=0
        for now_j in jewels:
            ans+=counter_stones[now_j]
        return ans

 

추가로 리스트 컴프리헨션을 통해 파이썬다운 풀이도 가능합니다.

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        return sum([(s in jewels) for s in stones]) #리스트 컴프리헨션을 의미하는 []생략가능

 

sum 내부가 [True, False, True, True]와 같은 리스트가 되고, sum을 할때, True는 1, False는 0으로 계산되어 갯수를 셀 수 있습니다.

<학습내용>

1. collections.Counter의 반환값인 Counter객체에서 존재하지 않는 키이면 0을 반환.
2. sum()에서 True와 False가 있을때, 각각 1,0으로 계산.

<학습이 필요한 내용>

1. 딕셔너리 관련 메소드들 모두 정리