[LeetCode] 771. Jewels and Stones

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

You're given strings jewels repersenting the types of stones that are jewels, and stones repersenting 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".

---

접근 방법: 딕셔너리

• stones 문자열을 순회하며 jewels 문자열에 포함된 문자인지 아닌지를 체크하여 count 변수값을 더해주는 방식으로 코드를 작성했다.

• stones 문자열에 포함된 문자를 카운트해주기 위해 collections 모듈에 Counter() 객체를 사용하였다.

• 이 후, jewels 문자열을 순회하며 카운트해준 값을 더해주었다.

class Solution:
    # collections.Counter() 사용
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        stones_table = collections.Counter(stones)
        count = 0
        for jewel in jewels:
            count += stones_table[jewel]
        return count

---

접근 방법: 리스트

• 딕셔너리를 사용하지 않고, 직접 두 문자열을 비교해 카운트를 셀 수도 있다.

class Solution:
    # in 사용
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        count = 0
        for stone in stones:
            if stone in jewels:
                count += 1
        return count

---

시간복잡도 비교

딕셔너리

• collections.Counter() 의 경우, 다음과 같이 구현할 수 있다. 전체 리스트를 한 번 순회하므로 시간복잡도는 $O(n)$이다.

list = [...]
dict = {...}

for item in list:
	if item not in dict:
    	dict[item] = 1
    else:
    	dict[item] += 1

• 또한 딕셔너리는 내부적으로 해시함수를 사용하고 있으므로 키를 이용하여 밸류를 찾는 연산의 시간복잡도 $O(1)$이다. 따라서 딕셔너리로 구현한 코드의 시간복잡도는 $O(n)$이 된다.

리스트

• 리스트의 경우, stones 를 돌면서 매 루프마다 jewels 에서 in을 사용하므로 총 시간복잡도는 $O(n^2)$이 된다.

• https://wiki.python.org/moin/TimeComplexity

---

• 문제에서는 주어진 문자열이 그렇게 길지 않아 런타임에 큰 차이가 있진 않았지만, 아마 문자열이 길어진다면 많은 차이가 날 것이라 생각한다.