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

https://leetcode.com/problems/jewels-and-stones/

Jewels and Stones - LeetCode

---

문제

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.

주어진 문자열 jewels는 보석의 종류를 나타내고, stones는 당신이 갖고 있는 돌의 종류를 나타낸다. 

각 stones의 문자는 당신이 갖고 있는 돌의 종류를 나타낸다. 당신은 갖고 있는 돌 중에 보석이 몇 개나 있을지 알고싶다.

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

대소문자 구분됨!

 

Example 1:

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

 

Example 2:

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

---

문제 이해

1. jewels와 stones의 문자를 하나씩 비교해서, 같은 것의 갯수를 세면 될 것 같다는 간단한 결론이 나왔다.

2. 문제 이해는 금방 했는데, 해시테이블을 오늘 배웠으니 해시 테이블을 사용해서 풀어야 할 것 같은데 어떻게 풀면 좋을까 ... 하는 생각을 더 오래 한 것 같다. 해설을 보니 해시 함수로 인덱스 처리를 해 주지 않아도 해시 테이블이라고 명명하는 것 같다.

---

문제 풀이 

1. 먼저 'table'이라는 빈 딕셔너리를 선언해준다. 이 딕셔너리는 돌의 종류를 key로 가지고, 해당 돌의 빈도수를 value로 가진다.

2. 'stones'의 각 돌에 대한 반복문을 수행하면서 (for문), 해당 돌이 'table' 딕셔너리에 이미 존재하는지 확인한다. (if문)

• 이미 존재하지 않는 경우, 새로운 key를 추가하고 빈도수를 1로 초기화한다.
• 이미 존재하는 경우, 해당 돌의 빈도수를 1 증가시킨다.

for stone in stones:		 
            if stone not in table:		
                table[stone] = 1		
            else:
                table[stone] += 1

3. 'jewels'의 각 보석에 대해 반복문을 수행하면서, 해당 보석이 'table' 딕셔너리에 존재하는지 확인한다.

• 존재하는 경우, 해당 보석의 빈도수를 'count'에 더해준다.

count = 0		# 변수 초기화
        for jewel in jewels:
            if jewel in table:			
                count += table[jewel]

4. 'count' 반환 

---

정답 코드

해시 테이블을 이용한 풀이

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        table = {} 		# table이라는 빈 딕셔너리 선언
 
        for stone in stones:		  # stones의 각 돌에 대해 반복문을 수행 > 해당 돌이 table 딕셔너리에 이미 존재하는지 확인
            if stone not in table:		# 테이블 안에 stone인덱스가 없다면,
                table[stone] = 1		# 해당 인덱스 생성 후 1 넣어준다.
            else:
                table[stone] += 1		# 테이블 안에 stone인덱스가 있는데 같은 값이 들어왔다면, +1
                
 	count = 0		# 변수 초기화
        for jewel in jewels:
            if jewel in table:			# table 안에 해당 인덱스를 골라서 count에 합산해줌
                count += table[jewel]
 
        return count

 

좀 더 파이써닉한 풀이

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        return sum(stone in jewels for stone in stones)		# for문을 한 줄로 적어 합친 코드

---

마치며

반복문 안에서 조건문 써줄 때 jewel을 jewels라고 했다가 wrong answer가 났었다 ..ㅎㅎ 정신차리고 하자잉 ^^7