[해시 테이블] 보석과 돌

771 | Jewels and Stones
https://leetcode.com/problems/jewels-and-stones/

 

 

 

작성 코드

 

 

문자열

 

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        answer = [stone for stone in stones if stone in jewels]
        return  len(answer)

 

• Time: 31 ms (88.27%), Space: 14 MB (41.27%) 
• stones for 문을 돌면서 jewels에 stone이 있는지 체크
• 문자열의 in 연산은 O(n)이므로 총 O(m*n)

 

 

set 연산 이용

 

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        jewel = set(jewels)
        
        answer = [stone for stone in stones if stone in jewel]
        return len(answer)

 

• Time: 49 ms (38.41%), Space: 13.9 MB (75.24%)
• set에서 in 연산은 O(1)이므로 총 O(m)

 

 

이상 코드

 

 

해시 테이블을 이용한 풀이

 

class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        freqs = {}
        count = 0

        # 돌(S)의 빈도 수 계산
        for char in S:
            if char not in freqs:
                freqs[char] = 1
            else:
                freqs[char] += 1

        # 보석(J)의 빈도 수 합산
        for char in J:
            if char in freqs:
                count += freqs[char]

        return count

 

• 돌의 빈도 수를 계산하여 dict에 저장해줌
• freqs[돌] = 돌의 개수
• 보석이 freqs에 있는지 확인하여 있다면 count에 돌의 개수를 더해줌
• 해시 테이블의 태그에 맞는 정석적인 풀이

 

 

해시 테이블을 이용한 풀이 - defaultdict 사용

 

class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        freqs = collections.defaultdict(int)
        count = 0

        # 비교 없이 돌(S) 빈도 수 계산
        for char in S:
            freqs[char] += 1

        # 비교 없이 보석(J) 빈도 수 합산
        for char in J:
            count += freqs[char]

        return count

 

• 이전 풀이에서 defaultdict를 사용함으로써 깔끔해짐

 

 

Counter 계산 생략

 

class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        freqs = collections.Counter(S)  # 돌(S) 빈도 수 계산
        count = 0

        # 비교 없이 보석(J) 빈도 수 합산
        for char in J:
            count += freqs[char]

        return count

 

• Counter을 이용하여 개수 계산에서 시간 줄임
• freqs = Counter({'b': 4, 'A': 2, 'a': 1})
• Counter은 존재하지 않는 키의 경우 에러 발생시키지 않고 0을 출력
• 보석을 돌면 freqs에 있는 값을 바로 가져오면 됨 / stone을 돌았다면 보석에 있는지도 체크했어야 됨

 

 

파이썬다운 방식

 

class Solution:
    def numJewelsInStones(self, J: str, S: str) -> int:
        return sum(s in J for s in S)