Jewels and Stones

돌을 한 번에 하나씩 살펴보세요. 각 돌마다 jewels를 훑으며 돌과 같은 첫 번째 문자를 찾으면 멈춥니다. 일치하면 개수에 1을 더합니다. 첫 번째 예시에서 돌 u는 r 및 R과 비교되지만 일치하는 문자가 없어 아무것도 더하지 않습니다.

보석 문자는 모두 서로 다르므로 돌 하나는 많아야 보석 문자 하나와 일치할 수 있습니다. 따라서 처음 일치하는 문자를 찾으면 멈춰도 됩니다. 보석이 아닌 돌은 그렇다는 것을 알기 전에 모든 보석 문자와 비교해야 합니다.

보석 종류가 j개이고 돌이 s개라면 비교 횟수는 최대 j × s회입니다. 여기서 j ≤ 52이므로 돌이 10^4개여도 비교 횟수는 약 5 × 10^5회이며, 탐색은 시간 내에 끝납니다. 종류 목록이 늘어나면 비효율이 드러납니다. 돌마다 같은 검색을 다시 수행하기 때문입니다.

"이 문자가 보석인가?"라는 질문은 같은 문자에 대해 물을 때마다 항상 같은 답이 나옵니다. 그러니 종류별로 한 번만 답하면 됩니다. jewels의 문자로 집합을 만드세요. 집합은 상수 시간에 포함 여부를 알려 주므로, 각 보석을 확인할 때 훑어보는 대신 조회 한 번이면 됩니다.

첫 번째 예제에서 집합은 {r, R}입니다. rubyRRr를 순회하면 조회 결과는 예, 아니요, 아니요, 아니요, 예, 예, 예입니다. 보석은 네 개입니다. 집합을 만드는 데 j단계가 걸리고 순회에는 s단계가 걸리므로, 총 시간은 O(j + s)입니다.

집합에는 최대 52개의 문자가 들어갑니다. 내장 집합이 없는 언어에서는 문자 코드로 인덱싱한 플래그 배열로 같은 작업을 할 수 있습니다.