ch11-2(leetcode 771). 보석과 돌

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 771번 ( https://leetcode.com/problems/jewels-and-stones/ )

 

풀이 1 : Counter

(교재를 참고하지 않은 풀이입니다.)

 

해시맵 단원의 문제인만큼 해시맵을 사용해서 풀 수 있다. 

파이썬의 딕셔너리 자료형은 내부적으로 해시맵으로 구현되어 있다. 또한 파이썬에는 딕셔너리를 상속받은, 즉 딕셔너리의 하위 클래스인 다른 클래스들도 있는데, 이 클래스들은 (key, value) 한 쌍을 저장하는 딕셔너리의 기본 특징에 더해서 추가적인 기능이 있다.

 

딕셔너리의 하위 클래스로는 Counter가 대표적이다. 

Counter는 초기화할 때 리스트나 문자열을 매개변수로 받을 수 있다. 이 경우 리스트나 문자열에 포함된 원소가 key, 해당 원소가 몇 번 나타났는지가 value가 된다. 그래서 문자열의 등장 빈도를 알고 싶다면 Counter으로 간단하게 계산할 수 있다. 

 

우선 stones 문자열을 매개변수로 사용해서 Counter 객체를 만들어 준다. 그러면 그 Counter 객체는 stones의 각 문자열을 key 값으로, 해당 문자열의 등장 빈도(숫자)를 value로 갖는다. 

또한 없는 문자열을 조회하려고 한다면 오류를 발생시키지 않고 0을 리턴한다. 

 

그리고 jewels에 대해 for loop를 돌려서, 각 jewels 알파벳의 value 값(=등장 빈도)를 모두 더한 뒤 리턴한다. 

 

전체 코드는 다음과 같다. 

class Solution(object):

    def numJewelsInStones(self, jewels, stones):
    
        counter = collections.Counter(stones)
        count = 0
        for j in jewels:
            count += counter[j]
        return count

 

풀이 2: 리스트 컴프리헨션(List Comprehension)

교재에서는 이 코드를 한 줄로 정리하는 방법도 제시한다. 

list comprehension을 이용하면 짧은 코드로 기존 리스트(jewels, stones)의 값을 이용해서 새 리스트들 만들 수 있다. 

def solution(self, jewels, stones):
	return sum(s in jewels for s in stones)