29. Jewels and Stones

리트코드

• J는 보석이며, S는 갖고 있는 돌이다. S에는 보석이 몇 개나 있을까?

  대소문자는 구분한다.

1. 해시 테이블을 이용한 풀이 (32ms / 14줄)

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        freqs = {}
        count = 0
        
        #돌(S)의 빈도 수 계산
        for char in stones:
            if char not in freqs:
                freqs[char] = 1
                
            else:
                freqs[char] += 1
                
        
        #보석(J)의 빈도 수 합산
        for char in jewels:
            if char in freqs:
                count += freqs[char]
                
        
        return count
        
   

• 갖고 있는 돌의 각각의 개수를 모두 헤아린 다음, 보석의 각 요소를 키로하는 각 개수를 합산하면 풀이할 수 있다.

• 먼저 freqs라는 해시 테이블을 선언한다.

  • 그리고 돌의 모음인 stones를 문자 단위로 하나씩 분리해 반복한다.

  • 만약 처음 등장한 문자라면 1을 선언하고, 기존에 있던 문자라면 1을 더한다.

  • 입력값 stones = 'aAAbbbb'는 해시 테이블 freqs에 다음과 같이 저장된다.

    {
        'a': 1.
        'A': 2,
        'b': 4
    
    }
    
    #각 문자별 빈도 수가 저장된다.

• 이 중에서 보석을 나타내는 jewels의 문자를 꺼내어 해당 문자의 빈도 수를 합하면 최종 결과가 된다.

  • 이 문제에서 보석 jewels의 입력값은 jewels = 'aA'이므로, freq['a']의 값 1과 freq['A']의 값 2를 더하면 최종 결과는 3이 될 것이다.

2. defaultdict를 이용한 비교 생략 (28ms / 10줄)

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        freqs = collections.defaultdict(int)
        count = 0
        
        #비교 없이 돌(stones)의 빈도 수 계산
        for char in stones:
                freqs[char] += 1
                
        
        #비교 없이 보석(jewels)의 빈도 수 합산
        for char in jewels:
                count += freqs[char]
                
        
        return count
        

• 키가 존재하는지 여부를 매번 판별할 필요가 없기 때문에 이처럼 바로 계산할 수 있고, 코드 수도 많이 줄어들어 깔끔해졌다.

3. Counter로 계산 생략 (32ms / 7줄)

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        freqs = collections.Counter(stones) # 돌(stones)의 빈도 수 계산
        count = 0
                
        
        #비교 없이 보석(jewels)의 빈도 수 합산
        for char in jewels:
                count += freqs[char]
                
        
        return count
        

• Counter를 사용하면 코드를 더욱 짧게 줄일 수 있다.

  • 각 개수를 계산하는 부분까지 자동으로 처리할 수 있기 때문이다.

• 아울러 Counter는 존재하지 않는 키의 경우 KeyError를 발생하는 게 아니라 0을 출력해주기 때문에, defaultdict와 마찬가지로 에러에 대한 예외 처리를 할 필요가 없다.

  • 단순히 jewels에 포함된 문자의 개수를 계산하기만 하면 된다.

4. 파이썬다운 방식 (28ms / 1줄)

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

• 각 문자를 하나씩 출력하는 리스트 컴프리헨션

>>> [s for s in stones]
['a', 'A', 'A', 'b', 'b', 'b', 'b']

• 여기에 약간 비교 구문을 추가해 stones의 문자 s가 jewels에 포함되어 있는지 여부를 출력할 수 있다.

>>>[s in jewels for s in stones]
[True, True, True, False, False, False, False]

• 이 값을 다음과 같이 sum 으로 합산한다.

>>>sum([s in jewels for s in stones])
3

• 리스트 컴프리헨션을 의미하는 대괄호 []는 제거 가능하다.

>>>sum(s in jewels for s in stones)
3