[leetCode] 771. jewels and Stones

문제

문제 해설

1. 보석(jewels)과 돌(stones)이라는 문자열이 제공된다.
2. 문자열 돌 중에 보석이 몇개 있는지 출력한다.
3. 소문자와 대문자는 서로 다른 종류의 돌로 간주한다.

 

---

문제 풀이

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        jewels_set = set(jewels) # 해시 셋을 생성하여 효율적인 검색을 위한 자료구조로 사용
        count = 0
        for stone in stones :
            if stone in jewels_set : # 돌이 보석인지 상수 시간 내에 확인
                count += 1
        return count

 

설명:

1. 해시 셋 생성:
   • jewels_set이라는 집합을 생성하여 고유한 보석을 저장합니다. 파이썬에서 집합은 해시 테이블로 구현되며, in 연산자를 사용하여 빠른 멤버십 검사를 제공합니다.
2. stones 문자열의 각 문자 (stone)를 순회합니다.
3. stone이 보석인지 확인합니다.
   • 현재 stone이 jewels_set에 있는지 in 연산자를 사용하여 효율적으로 확인합니다. 해시 테이블의 구조로 인해 이 검색은 상수 시간에 수행됩니다.
4. 보석을 세웁니다.
   • stone이 실제로 보석이라면 count를 1 증가시킵니다.
5. 모든 돌을 순회한 후 발견한 보석의 최종 개수 count를 반환합니다.

핵심 포인트:

• 해시 테이블: 효율적인 멤버십 검사에 탁월하여 이 문제에 이상적입니다.
• 시간 복잡도: O(m + n), 여기서 m은 jewels의 길이이고 n은 stones의 길이입니다.
• 공간 복잡도: jewels_set을 저장하기 위한 O(m)