[파이썬 알고리즘 인터뷰][해시테이블] 보석과 돌

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

 

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

입력받은 두 문자열 jewels, stones에 대해, jewels의 각 문자들이 stones에 포함된 개수의 합

 

책에서 구현된 코드

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

 

기억해야할 기법

• Boolean을 1과 0으로 인식 가능
  
  • True + True -> 2
• 문제 접근 방식
  • Stone의 문자를 중심으로 True / False의 합을 구함
• sum에서 리스트 기호([]) 없이 되는 이유?
  • s in J for s in S의 return은 Generator
  • Generator는 기본 표현은 parenthesize (괄호 안에 있어야함)
  • for문만 예외? (다음에 알아보자)
    https://stackoverflow.com/questions/9297653/python-generator-expression-parentheses-oddity

Python generator expression parentheses oddity

 

내가 구현한 코드

def numJewelsInStones(jewels: str, stones: str) -> int:
    count = Counter(stones)
    return sum([ count[j] for j in jewels if count.get(j) ])

• 해시 테이블을 사용하지 않은 책의 코드와 속도가 비슷함