[파이썬 알고리즘] 보석과 돌

보석과 돌

리트코드로 풀러 가기

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

입력
J = "aA", S = "aAAbbbb"

출력
3

---

해시 테이블

S를 문자 단위로 분리한 결괏값을 각각의 갯수를 헤리아리는 형태로 딕셔너리(해시 테이블)에 입력시킨다.

그 후, 보석인 인덱스들의 값을 합쳐주면 간단한 풀이가 완성된다.

def numJewelsInStones(self, jewels, stones):
    freqs = collections.defaultdict(int)
    result = 0

    for char in stones:
        freqs[char] += 1

    for char in jewels:  # !
        result += freqs[char]

    return result

defaultdict를 이용해 요소가 딕셔너리에 없을 때의 조건을 생략하여 구현했다.

만약, 일반 딕셔너리를 이용하여 구현한다면, # ! 부분에서

if char in freqs:

위와 같은 조건으로 키가 없을때 수행하지 않게끔 처리를 해주어야 한다.

Counter 객체 활용

def numJewelsInStones(self, jewels, stones):
    freqs = collections.Counter(stones)  # 빈도 수 계산
    result = 0

    for char in jewels:
        result += freqs[char]

    return result

Counter이 존재하지 않는 키에 대해서 0을 출력해주기 때문에, 예외 처리를 할 필요가 없다.

'파이썬' 스러운 풀이

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

다소 이해하기 난해하나,

s(첫번째)가 stones에 있는지를 검사하며, 그 s(두번째)는 각 jewels에 있는 요소이다.

라고 풀어서 설명할 수 있다.

결과는 [true, false, true ...] 와 같은 형태의 리스트가 되며, sum 계산을 통해 true의 갯수가 return 된다.

전체 코드: numJewelsInStones.py