29. Jewels and Stones

🎯 leetcode - 771. Jewels and Stones

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 29번 문제

📌 날짜

2020.02.01

📌 시도 횟수

1 try

💡 Code

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        stone_dict = defaultdict(int)
        count = 0
        for stone in stones:
            stone_dict[stone] += 1

        for jewel in jewels:
            count += stone_dict[jewel]

        return count

💡 문제 해결 방법

- defaultdict를 사용해 stones의 종류와 개수를 담았다.
- jewels가 stone_dict에 존재하면 해당 개수(value)를 count에 더했다.
- 최종적으로 count를 리턴!

💡 새롭게 알게 된 점

-

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 

---

😉 다른 풀이

📌 하나. Counter으로 계산 생략하기

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        freqs = Counter(stones)
        count = 0
        print(freqs) # 디버깅용       
        for j in jewels:
            count += freqs[j]
        return count

➡ INPUT EXAMPLE

• jewels = "abcd"
• stones = "AAbbCCdd"

➡ OUTPUT EXAMPLE

• Counter({'A': 2, 'b': 2, 'C': 2, 'd': 2})
• count = 4

💡 새롭게 알게 된 점

- Counter의 경우 존재하지 않는 키를 부르면 KeyError을 발생시키지 않고 0을 반환한다.
- 따라서 이에 대한 예외 처리가 필요하지 않아 간편하다.

🌵 collections.Counter()

1. Create a new, empty Counter object.
2. And if given, count elements from an input iterable.
3. Or, initialize the count from another mapping of elements to their counts.

---

➡ INPUT

c = Counter()  # a new, empty counter
c = Counter("gallahad")  # a new counter from an iterable
c = Counter({"a": 4, "b": 2})  # a new counter from a mapping
c = Counter(i=4, j=2)

➡ OUTPUT

Counter()
Counter({'a': 3, 'l': 2, 'g': 1, 'h': 1, 'd': 1})
Counter({'a': 4, 'b': 2})
Counter({'i': 4, 'j': 2})

---

📌 둘. 리스트 컴프리헨션 이용하기

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

💡 새롭게 알게 된 점

✔ 리스트 컴프리헨션
- 예를 들어 jewels = "abcd", stones = "AAbbCCdd"라고 하자.

>> [item for item in stones]
['A', 'A', 'b', 'b', 'C', 'C', 'd', 'd']

>> [item in jewels for item in stones]
[False, False, True, True, False, False, True, True]

---------------------------------------------------------
✔ 파이썬 True, False와 sum 함수
- True는 정수 값으로 1, False는 0이다.

>> int(True)
1
>> int(False)
0
>> sum([True, True, False])
2