Hyuntae H

Hyuntae H

배워가는 학생
21.03.29~22.09.28 군대

Python Algorithm Q29

Q29 Jewels and Stones

Q

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”.

Sample Input

Input: jewels = “aA”, stones = “aAAbbbb”
Output: 3

Input: jewels = “z”, stones = “ZZ”
Output: 0

Constraints

  • 1 <= jewels.length, stones.length <= 50
  • jewels and stones consist of only English letters.
  • All the characters of jewels are unique.

1. My Own Solution

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        jewlist= list(jewels)
        stcnt = collections.Counter(stones) #key(alphabet) : value(number)
        ans = 0

        for x in jewlist: #if exists, not 0
            #if stcnt[x] != 0: #refer to the description below
            ans += stcnt[x]

        return ans

직관적이고 생각나는대로 푼 내 풀이이다. 코드는 대충 봐도 알아먹기 쉽다. 근데 그래서인지 런타임이랑 메모리 소모율이 썩 좋지는 않은 것 같다. 아마 counter 만드는 것 때문에 런타임이 다소 길어지지 않았을까.

*보충 설명 : counter 모듈을 이용한다면 존재하지 않는 키의 경우 KeyError를 발생하는게 아니라 0을 출력해주기 때문에 주석 처리해둔 것 처럼 if문을 굳이 사용하지 않아도 된다.

2. Given Solution #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        freq = {}
        cnt = 0

        #substitute counter module
        for a in list(stones):
            if a not in freq:
                freq[a] = 1 #append new one
            else:
                freq[a] += 1

        #start counting with jewels
        for b in list(jewels):
            num = freq[b]
            if num != 0:
                cnt += num

        return cnt

책에 있던 풀이이다. 근데 내 풀이랑 사실 다를게 없다. 그냥 내가 귀찮아서 Counter Module을 쓴 것을 풀어서 만든 것 뿐이다. 그래서 런타임도 비슷하게 찍힌다. 시간 복잡도는 counter 구현 과정에서 n, 그리고 jewel searching 과정에서 n 즉 O(n).

3. Given Solution #2

1
2
3

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

책에서 소개한 “파이썬다운” 방식이다. 해석해보면 sum(s in J, for s in S) 정도로 볼 수 있겠다. list comprehension을 이용한 방식인데 작동 과정은 다음과 같다. 먼저 [s for s in S]를 통해서 (example 1 참고)

[‘a’, ‘A’, ‘A’, ‘b’, ‘b’, ‘b’, ‘b’]

를 얻을 수 있다. 이제 여기서 in J를 넣으면 매 번 위 element 들이 J에 존재하는지 확인하고 boolean으로 결과를 출력해준다. 즉

[True, True, True, False, False, False, False]

이다. 당연히 boolean 값은 int 상으로 1과 0이므로 합하면 3을 얻을 수 있다.

4. Given Solution #3

1
2
3
4
5
6
7

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        jewelset=set(jewels)
        cnt=0
        for element in jewelset:
            cnt += stones.count(element)
        return cnt

런타임이 비교적 짧은 풀이이다. jewel string을 풀어헤쳐서 set으로 만드는 과정은 O(1)이고, 코드 전체에 for문은 단 하나뿐이므로 위에 풀이들에 비해(O(2n)) 상대적으로 시간이 덜 소요된다(O(n)). 앞서 말했듯 먼저 set으로 분해 시킨 후에, stones 안에 set의 element가 몇 개나 들어있는지 다 더해준다.

Overall Review

문제는 굉장히 쉽다. 정답률이 85퍼에 육박한다. 하지만 알고리즘을 달리하는 것만으로 미약하지만 시간적 측면에 있어서 우위를 얻을 수 있다. 메모리 사용량은 얼마 차이나지도 않은데 시간이 꽤 줄어든다. 일반적으로 시간과 메모리는 반비례 관계인데 알고리즘 하나만으로 일방적인 이득을 얻었다.

참고