Python 알고리즘 인터뷰 - 문제 29. 보석과 돌

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

 

J는 보석이며, S는 갖고 있는 돌이다. S에는 보석이 몇개나 있을까? 대소문자는 구분한다.

예제

입력

J = "aA", S = "aAAbbbb"

 

출력 

3

 

풀이

파이썬의 Counter 딕셔너리를 사용하면 S 문자열이 문자별 개수를 구할 수 있다. J의 각 문자를 순회하면서 해당 문자를 key 값으로 Counter에 value, 즉 개수를 더해나가면 간단히 보석의 개수를 구할 수 있다. 코드는 다음과 같다.

def numJewelsInStones(jewels: str, stones: str):
    counter = collections.Counter(stones)
    count = 0
    for jewel in jewels:
        count = count + counter[jewel]

    return count

 

Python의 리스트 컴프리헨션을 사용하면 좀더 Pythonic 하게 코드를 작성할 수 있다. 

def numJewelsInStones(self, jewels, stones):
    return sum(stone in jewels for stone in stones)

 

 

코드를 풀어서 정리해보도록 한다.

먼저 [stone for stone in stones]의 출력은 다음과 같다.

 

>>> [stone for stone in stones]

['a', 'A', 'A', 'b', 'b', 'b', 'b']

 

위의 stones의 문자열을 문자 리스트로 생성해준다. 여기서 [stone in jewels for stone in stones]을 추가해주면 각 stone 문자에 대해서 jewels에 포함되는지 Boolean형태(True/False)로 반환해준다. 출력은 다음과 같다. 

 

>>> [stone in jewels for stone in stones]

[True, True, True, False, False, False, False]

 

 sum함수에서는 리스트 컴프리핸션을 의미하는 []를 제거할 수 있으며, sum(stone in jewels for stone in stones)으로 호출할 수 있다.

 

sum 함수는 리스트에서 True를 1로, False를 0으로 취급하여 덧셈을 진행한다. 따라서 결과는 3이 된다.