May LeetCoding Challenge[Day2] - Jewels and Stones

You're given strings J representing the types of stones that are jewels, and S representing the stones you have.  Each character in S is a type of stone you have.  You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Note:
S and J will consist of letters and have length at most 50.
The characters in J are distinct.

Input: J = "aA",
S = "aAAbbbb" Output: 3

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 2개의 input 값이 주어진다.

 - J는 캘 수 있는 돌의 종류, S는 캐야하는 돌들을 input으로 제공받는다.

 - 2개의 input 값은 string으로 받기 때문에, 해당 string을 탐색할 수 있도록, char[] 형으로 변경해준다.

 - 이 때, 내가 캐야하는 돌들에 특정 돌이 존재하는 지 확인해야한다.

 - 어떻게 돌을 탐색할 지, 정해야하기 때문에 O(1)로 검색하기 위해서, HashSet을 사용했다.

 - HashSet의 contains를 활용해서 key값을 기준으로, 검색해준다. 이 때, S로 캐야하는 돌들의 길이만큼 돌려주기 때문에 O(N)의 시간 복잡도를 갖게 된다.

 

2. 알고리즘 작성 중, 어려운 점

 

 - 왜, 1ms까지 땡기지 못 할까? 라고 생각을 했다.

 - 런타임에 따라서 결과가 변했어서, 최종적으로 맞는 답이라고 생각을 했다. 

 

3. 내가 작성한 알고리즘

class Solution {
    public int numJewelsInStones(String J, String S) {
        int count = 0;
        char[] jArray = J.toCharArray();
        char[] splits = S.toCharArray();
        
        Set<Character> hashSet = new HashSet();
        for(int i=0; i<jArray.length; i++){
            hashSet.add(jArray[i]);
        }
        
        for(int i=0; i<splits.length; i++){
            if(hashSet.contains(splits[i])){
                count++;
            }
        }
        return count;
    }
}

4. 내가 작성한 알고리즘 결과

런타임 시간이 1~3ms까지 왔다 갔다~

 

 

문제 : https://leetcode.com/explore/featured/card/may-leetcoding-challenge/534/week-1-may-1st-may-7th/3317/

Account Login - LeetCode