[leetcode] 29. 보석과 돌 (Jewels-and-stones)

들어가며

본 포스팅은 <파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 다루고 있습니다. 

문제들은 모두 리트코드에서 출제된 문제들이며, 문제 풀이의 많은 부분을 책의 힌트와 해설을 참고하였습니다. 

 

포스팅되는 모든 문제들의 목록과 풀이는 파이썬 알고리즘 인터뷰에서 제공하는 깃허브에서 확인하실 수 있습니다.

 

---

문제

You're given strings jewels representing the types of stones that are jewels, and stones representing the stones you have. Each character in stones is a type of stone you have. You want to know how many of the stones you have are also jewels.

Letters are case sensitive, so "a" is considered a different type of stone from "A".

 

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

 

 

입출력 예시

Example 1:

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

Example 2:

Input: jewels = "z", stones = "ZZ"
Output: 0

 

생각과정

J와 S의 문자열을 하나씩 비교해서 서로 같다면 갯수를 센 다음 합해주는 간단한 풀이.

 

풀이

내 풀이는 중첩 for문을 사용했고, 오늘 배운 해시 테이블도 사용하지 않은 풀이이다.

def numJewelsInStones(J: str, S: str) -> int:
    sum = 0

    for j in J:
        count = 0

        for s in S:
            if j == s:
                count += 1

        sum += count

    return sum

크게 설명할 부분 없이 j와 s가 같다면 count에 1을 추가해주는 반복문을 돌고 sum에 담아준다. 돌과 보석을 비교한는 for문이 끝나면 sum에 합쳐주고 리턴해주면 끝.

 

그럼 해설지에 있는 해시 테이블을 이용한 풀이를 보자

def numJewelsInStones(J: str, S: str) -> int:
    # 테이블 선언
    freqs = {}

    for char in S:
        # 테이블 안에 char 인덱스가 없다면, 해당 인덱스를 생성하고 1을 넣어준다. char not in freqs는 key값이 있는 지 확인하는 조건문이다.
        if char not in freqs:
            freqs[char] = 1
        # 테이블 안에 char 인덱스가 있는데 또 같은 값이 들어왔다면, +1을 해준다.
        else:
            freqs[char] += 1

    count = 0
    for char in J:
        # 테이블 안에 해당 인덱스를 골라서 count에 합산해준다.
        if char in freqs:
            count += freqs[char]


    return count

조금 길어보이지만 결국 로직은 비슷하다. 

 

해시 테이블을 먼저 생성해준 후, 돌맹이를 하나씩 꺼내준다. 첫번째 if문은 else문에서 freqs[char] += 1에서 key값이 없는 테이블을 조회할 때 나타나는 에러를 막기 위해 짜여진 코드로, 테이블 안에 key가 없으면 1개를 넣어준다.

그 다음 else문에서 같은 글자가 또 나오면 해당 key에 1개의 돌맹이를 추가해준다.

 

모든 돌맹이를 freqs에 추가해주었으면 보석이 freqs안에 있을 때만 count를 해주어서 결과 값을 리턴해준다.

 

처음에 if문으로 인덱스 에러를 방지해주는 부분을 collections.defaultdict(int)로 처리할 수 있는데, 코드를 보자

def numJewelsInStones(J: str, S: str) -> int:
    freqs = collections.defaultdict(int)
    count = 0

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

    for char in J:
         count += freqs[char]

    return count

해시 테이블에 돌맹이가 없을 경우에 요소를 하나 추가해주는 구문이 빠졌다. 이렇게 한줄이 줄어들었다. 나머지 로직은 같으니 이번엔 돌맹이를 테이블에 넣어주는 코드도 없애보자

 

def numJewelsInStones(J: str, S: str) -> int:
    freqs = collections.Counter(S)
    count = 0

    for char in J:
        count += freqs[char]

    return count

이번엔 collections.Counter(s)로 아예 처음부터 자동으로 테이블을 만들어줬다. 매우 간단한 코드가 되었다.

 

 

---

마치며

너무 쉬운 문제였다. 이런거만 풀 줄 알면 안되는데....