파이썬 알고리즘 인터뷰 - 보석과 돌

문제

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

"가지고 있는 돌이있는데, 그 안에서 보석이 몇 개나 있는지 구하는 문제"

제한사항 - 리트코드

1 <= jewels.length, stones.length <= 50 -> 보석의 길이가 1 이상, 돌의 길이는 50 이하

jewels and stones consist of only English letters. -> 보석과 돌은 영문으로 되어 있음, 대소문자 구분

All the characters of jewels are unique. -> 보석은 중복되는 문자가 없다, 최대 26+26 = 52

입력

jewels = "aA"
stones = "aAAbbbb"

출력

3

작성한 코드

def numJewelsInStones1(jewels: str, stones: str) -> int:
    cnt = 0
    # 돌에있는 값들로 for문을 돌릴건데
    for s in stones:
        # 그 값중에 보석안에 존재하는 값이면 카운팅
        if s in jewels:
            cnt+=1

    return cnt

* 리트코드에 제출 했을 때, 36 ms 13.9 MB

해시 테이블로 이용한 풀이

def numJewelsInStones2(jewels: str, stones: str) -> int:
    # 딕셔너리 선언
    freqs = {}
    count = 0

    # 돌에 있는 값을 하나씩 꺼내서 딕셔너리에 담아서 빈도수를 계산
    for s in stones:
        if s not in freqs:
            freqs[s] = 1
        else:
            freqs[s] += 1

    # freqs = {'a': 1, 'A': 2, 'b': 4}

    for j in jewels:
        if j in freqs:
            # 체크해둔 빈도수랑 보석이랑 비교해서 카운팅 하는 방법
            count += freqs[j]

    return count

defaultdict를 이용한 비교 생략

def numJewelsInStones3(jewels: str, stones: str) -> int:
    freqs = collections.defaultdict(int)
    count = 0

    # 조건절 없이 빈도 수 계산
    for s in stones:
        #if s not in freqs:
        #freqs[s] = 1
        #else:
        freqs[s] += 1

    # freqs = {'a': 1, 'A': 2, 'b': 4}

    for j in jewels:
        if j in freqs:
            count += freqs[j]

    return count

* defaultdict을 사용하여 존재하지 않는 키에 대한 오류를 막아서, 비교하는 과정을 생략

* 사용하지 않으면 KeyError: 'a' 이런식으로 오류가 남

Counter로 빈도수 계산 생략

def numJewelsInStones4(jewels: str, stones: str) -> int:
    #collections 모듈의 Counter 클래스
    #stones을 카운터 함수에 담으면 각각의 인자들의 빈도수를 카운팅
    freqs = collections.Counter(stones)
    # print(freqs)
    # Counter({'b': 4, 'A': 2, 'a': 1})
    count = 0

    for j in jewels:
        count += freqs[j]

    return count

파이썬 다운 방식

def numJewelsInStones5(jewels: str, stones: str) -> int:

    # lst = [s in jewels for s in stones]
    # print(lst)
    # [True, True, True, False, False, False, False]
	# 컴프리헨션
    return sum(s in jewels for s in stones)

 

리트코드에서 확인

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

Jewels and Stones - LeetCode

회고

여러가지 경우로 풀어봤는데, 책에서 나왔듯이 시간복잡도는 비슷

그래서 어떤 방식으로 풀어도 무관한 문제이다.

"리스트 컴프리헨션 이해하기"

https://wikidocs.net/22805

1) 리스트 컴프리헨션