[파이썬 알고리즘] 11장 - 보석과 돌 (defaultdict, Counter 사용)

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

Jewels and Stones - LeetCode

<문제>

You're given strings jewels representing the types of stones that are jewels, and stones representing the stones you have. Each character in stones is a type of stone you have. You want to know how many of the stones you have are also jewels.

Letters are case sensitive, so "a" is considered a different type of stone from "A".

 

<예시>

Input: jewels = "aA", stones = "aAAbbbb" Output: 3

Input: jewels = "z", stones = "ZZ" Output: 0

 

---

1. 파이썬에서 제공하는 dictionary 자료형을 이용한 풀이

import collections

# 나의 솔루션
class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:

        stone_to_num = {}
        total_jewels = 0

        for stone in stones:
            if stone in stone_to_num:
                stone_to_num[stone] += 1
            else:
                stone_to_num[stone] = 1

        for jewel in jewels:
            if jewel in stone_to_num:
                total_jewels += stone_to_num[jewel]
        return total_jewels

 

2. defaultdict을 이용한 풀이

• 주어진 객체의 기본값을 딕셔너리의 초기값으로 지정할 수 있다.
• 여기서는 collections.Counter(int)를 사용하여 기본값을 0으로 주었다.
• 이 외에도 list, set 등으로도 초기값을 부여할 수 있다!

class Solution2:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:

        stone_to_num = collections.defaultdict(int) # int의 기본값을 딕셔너리의 초기값으로 지정
        total_jewels = 0

        for stone in stones:
            stone_to_num[stone] += 1
        for jewel in jewels:
            total_jewels += stone_to_num[jewel]
        return total_jewels

 

3. Counter를 이용한 풀이

class Solution3:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:

        stone_to_num = collections.Counter(stones)
        total_jewels = 0

        for jewel in jewels:
            total_jewels += stone_to_num[jewel]
        return total_jewels

 

4. pythonic한 풀이

# pythonic solution
class Solution4:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        return sum(stone in jewels for stone in stones)