[알고리즘][해시 테이블] - 2. 보석과 돌

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/jewels-and-stones/submissions/

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

---

[보석과 돌]

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        freqs = {}
        cnt = 0 
        
        for i in stones:
            if i not in freqs:
                freqs[i] = 1
            else:
                freqs[i] += 1
                
        #갯수 합산
        for i in jewels:
            if i in freqs:
                cnt += freqs[i]
        return cnt

stones = "aAAbbbb"

 

freqs = {

                'a':1

                'A':2

                'b':4

}

 

• 저장한 stones를 키로 넣고 갯수를 키값으로 넣어 쥬얼리에 이 값이 있으면 키값을 cnt에 더해주면 답이 나온다.

[defaultdict를 이용한 비교 생략]

import collections


class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        freqs = collections.defaultdict(int)
        cnt = 0

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

        #갯수 합산
        for i in jewels:
            cnt += freqs[i]
        return cnt

• 키 존재 여부를 매번 판별할 필요가 없어 바로 계산이 가능하다.

[counter로 계산 생략]

import collections


class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        freqs = collections.Counter(stones)
        cnt = 0
        for i in jewels:
            cnt += freqs[i]
        return cnt

[파이썬다운 방식]

import collections


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

• 돌을 돌면서 쥬얼리가 있으면 더해주는 과정을 한 줄로 나타냄.

[실행속도]

• 위의 코드 순서대로 실행속도와 메모리를 얼마나 사용했는지 보여주는 것이다.