11장. 해시 테이블(4) - 예제(보석과 돌)

 

문제. 보석과 돌

J는 보석이며, S는 갖고 있는 돌이다. S에는 보석이 몇 개나 있을까? 이때, 대소문자는 구분한다. 
입력: J ="aA", S = "aAAbbbb"
출력: 3

 

 

 

풀이1. 해시 테이블을 이용한 풀이

이 문제는 S의 각 문자 빈도를 해시 테이블로 계산한 후, J의 각 문자에 해당하는 빈도 수를 더하는 방식으로 해결할 수 있다.

 

S = "aAAbbbb"

freqs = {}

for char in S:
    if char not in freqs:
        freqs[char] = 1
    else:
        freqs[char] +=1
        
freqs  # {'a': 1, 'A': 2, 'b': 4}

 

 

1. S의 각 문자가 몇 번씩 등장하는지 세기 위해 해시 테이블을 생성한다.
2. S의 문자를 순회하며 각 문자의 빈도를 해시 테이블에 저장한다.
3. 해시 테이블에 빈도가 저장되면, J의 문자를 하나씩 순회하면서 해당 문자가 해시 테이블에 있다면 빈도를 누적하여 더한다.

 

이렇게 하면 각 문자의 빈도수를 효과적으로 저장하고, J의 문자에 해당하는 빈도수만 골라 더할 수 있다.

 

J = "aA"

count = 0

for char in J:
    if char in freqs:
        count += freqs[char]
        
count   # 3

 

[전체 코드]

def numJewelsInStones(self, J:str, S:str) -> int:
    
    count = 0
    freqs = {}
    
    for char in S:
        if char not in freqs:
            freqs[char] = 1
        else:
            freqs[char] +=1
            
    for char in J:
        if char in freqs:
            count += freqs[char]
            
    return count

 

 

이 방식의 장점은 S의 문자를 모두 한 번씩만 순회하기 때문에 효율적이라는 점이다.

그러나 조건문을 통해 키 존재 여부를 계속 확인해야 하므로 약간의 코드 개선 여지가 있다. 

 

---

풀이2. defaultdict를 이용한 비교 생략

defaultdict를 사용하면 새로운 키가 발생할 때 자동으로 초기값을 지정할 수 있다.

이 문제에서는 숫자 0을 기본값으로 설정하여, 존재하지 않는 키를 만났을 때도 비교 없이 바로 빈도를 누적할 수 있다.

import collections

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

1. defaultdict로 빈도 저장용 테이블을 생성한다. 기본값을 int로 지정하여 새로운 키가 생기면 0으로 초기화된다.
2. S의 각 문자 빈도를 계산할 때, 조건문 없이 빈도만 누적한다.
3. J의 문자를 순회하며 해당 빈도를 더해준다.

이 방법은 조건문이 사라져 코드가 더 간결해지고, 불필요한 존재 확인을 피할 수 있다.

 

---

 

 

 

풀이3. Counter로 계산 생략

Counter는 Python 표준 라이브러리 collections에 포함된 특수 자료형으로, 각 요소의 빈도를 자동으로 세어주는 해시 테이블이다.

import collections

def numJewelsInStones(self, J:str, S:str) -> int:
    
    freqs = collections.Counter(S)   # Counter({'b': 4, 'A': 2, 'a': 1})
    count = 0
    
    # 비교 없이 보석 빈도 수 합산
    for char in J:
        count += freqs[char]
        
    return count

 

 

• Counter(S)를 통해 S의 각 문자 빈도를 계산하여 freqs에 저장한다.
• J의 문자를 순회하며 빈도를 누적한다.

 

Counter는 존재하지 않는 키에 대해 기본값 0을 반환하기 때문에, 에러 예외 처리가 필요 없고 코드도 더 간결해진다.