[리트코드] Jewels and Stones(python)

리트코드, Jewels and Stones_보석과 돌

 

TL;DR

• 해시(해시 테이블/맵, 딕셔너리)을 사용하여 주어진 문제를 풀 수 있는지

문제 분석

1. jewels : 각 글자는 보석에 해당하는 돌을 나타낸다.
2. stones : 각 글자는 내가 보유하고 있는 돌을 나타낸다.
3. 내가 갖고 있는 돌 중 보석이 몇 개나 있는지를 반환하라.
4. 'a'와 'A'는 서로 다른 종류의 돌로 간주한다.

 

- 내가 보유하고 있는 돌인 stones에서 jewels에 있는, 보석인 돌을 얼마나 갖고 있는지를 파악하는 문제이다.

- 내가 보유한 돌의 종류를 key로, 돌의 개수를 value로 하는 딕셔너리(dictionary)로 생각하면 문제를 해결할 수 있다.

입출력 형태

입출력 예시

 

- 예시 1

    - 내가 보유한 돌은 a 1개, A 2개, b 4개이다.

    - 이 중 보석인 돌은 a와 A이다.

    - 따라서 내가 보유하고 있는 돌 중 보석인 돌은 a와 A이므로, 3을 반환한다.

- 예시 2

    - 내가 보유한 돌은 Z 2개이다.

    - 이 중 보석인 돌은 z로, 내가 보유한 돌에는 없다. 따라서 0을 반환한다.

풀이

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        stone_counter = Counter(stones)
        answer = 0
        
        for jewel in jewels:
            answer += stone_counter[jewel]
            
        return answer

 

- collections.Counter는 배열에 있는 원소를 key로, 개수를 value로 하는 딕셔너리이다. 이를 통해 손쉽게 각 돌의 개수를 얻어낼 수 있다.

- jewels의 원소를 key로 Counter를 조회하면 답을 얻어낼 수 있다.

개선된 풀이

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        return sum([s in jewels for s in stones])

 

- 현재 공부하고 있는 책인 '파이썬 알고리즘 인터뷰'에서 제안하는 보다 파이썬스러운(pythonic)한 풀이 방법을 소개하려고 한다.

- 내가 보유한 돌들인 stones에서 각 돌이 jewels에 들어 있는지 확인한다.

    - 이 때, 돌이 존재한다면 배열에 True가 없다면 False가 추가된다.

- 따라서, 배열의 합은 더하게 되면 True인 값만 더해져서 동일한 결과를 얻을 수 있다.