파이썬으로 풀어보는 보석과 돌(Jewels and Stones) 문제

문제 소개

문자열 J는 보석(Jewel)으로 간주되는 문자들의 목록을 나타내고, 문자열 S는 현재 가지고 있는 돌(Stone)들을 의미합니다. 이 문제의 목표는 돌 문자열 S에 포함된 문자 중, 보석 문자열 J에도 해당하는 것이 몇 개인지 세는 것입니다.

여기서 주의할 점은 대소문자를 구분한다는 것입니다. 즉, 'a'와 'A'는 서로 다른 문자로 취급됩니다.

예시

• J = "aZc" → 보석은 'a', 'Z', 'c'
• S = "catTableZebraPicnic"
• 결과: 보석에 해당하는 문자가 총 7개

해결 접근 방법

가장 직관적인 방법은 다음과 같습니다.

1. 문자열 J의 각 문자를 딕셔너리(해시 맵)에 저장하여 빠른 조회를 가능하게 합니다.
2. 문자열 S를 한 글자씩 순회하면서, 해당 문자가 딕셔너리에 존재하면 카운트를 1씩 증가시킵니다.
3. 최종 카운트 값을 반환합니다.

딕셔너리를 사용하면 각 문자의 존재 여부를 평균 O(1) 시간에 확인할 수 있어 전체 탐색이 매우 효율적입니다.

구현 예제

class Solution(object):
    def numJewelsInStones(self, J, S):
        # 보석 문자들을 딕셔너리에 저장
        jewels = {}
        for i in J:
            jewels[i] = 1
        
        number = 0
        # 돌 문자열을 순회하며 보석 여부 확인
        for i in S:
            if i in jewels:
                number += 1
        return number

ob1 = Solution()
print(ob1.numJewelsInStones("aZc", "catTableZebraPicnic"))

입력

"aZc"
"catTableZebraPicnic"

출력

7

더 간결한 대안 코드

파이썬의 집합(set)과 내장 함수를 활용하면 위 로직을 한 줄로 표현할 수도 있습니다.

def numJewelsInStones(self, J, S):
    jewel_set = set(J)
    return sum(stone in jewel_set for stone in S)

복잡도 분석

• 시간 복잡도: O(N + M) — N은 문자열 J의 길이, M은 문자열 S의 길이입니다.
• 공간 복잡도: O(N) — 보석 문자를 저장하기 위한 자료구조 공간입니다.