[Leetcode] 771. Jewels and Stones

✅ 문제 - 보석과 돌

 

이 문제는 두 문자열을 비교하여 jewels에 있는 문자들이 stones에서 몇 번 나왔는지 카운팅하는 문제이다.

 

---

 

✅ 풀이

여러 가지 방법을 생각해 봤는데,

1차원적으로는 각각 반복문을 돌면서 일치여부를 확인해서 카운팅을 하는 방법이다. 이 경우에는 중첩for문이 들어가게 돼서 시간복잡도가 증가한다.

 

stones에 나온 문자들만 카운팅을 따로 해서 해시 테이블 구조로 만들어 주면 key값으로 해당하는 문자가 몇 번 나왔는지 조회할 수 있어 훨씬 간단해진다.

 

 

방법1) 

💡 Point
1. 딕셔너리 이용하여 stones의 문자를 key로 묶어 해싱
2. jewels의 문자를 key값으로 가지는 value(몇 번 나왔는지)를 answer에 더하여 반환

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        
        # 빈 값이 있을 경우 default값으로 딕셔너리 생성
        # stones에 문자 몇 번씩 나왔는지 체크
        count = collections.defaultdict(int)
        
        #카운팅 할 답
        answer = 0
        
        # stones의 문자들을 key로 묶어 카운팅해주는 작업
        for char in stones:
            count[char] += 1
         
        # jewels의 문자가 count 테이블에 있다면
        # 그 문자를 key값으로 가지는 value를 answer에 더해줌
        for char in jewels:
                answer += count[char]
        
        return answer

 

---

 

방법2)

하지만 더 간편한 방법이 있다.

defaultdict 딕셔너리를 선언 후 for문을 돌면서 해싱하는 작업을 counter 하나로 줄일 수 있다. 사실상 같은 효과이다.

따라서 코드는 아래와 같이 변경된다.

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        
        count = collections.Counter(stones)
        
        #카운팅 할 답
        answer = 0
           
        # jewels의 문자가 count 테이블에 있다면
        # 그 문자를 key값으로 가지는 value를 answer에 더해줌
        for char in jewels:
                answer += count[char]
        
        return answer

 

 

해싱하는 방법은 다르지만 결과적으로는 아래와 같이 둘 다 같은 테이블이 생성이 된다!