[LeetCode/EASY] 771. Jewels and Stones (JAVA) : 문제&풀이

 

 

stones 문자열로부터 jewels가 몇 개 포함되었는지 찾는 문제이다.

 

두 String을 매개변수로 받는 solve 메서드의 틀이 주어진다.

 

Problem : 

public class JewelsAndStones {
    public int solve(String jewels, String stones) {

    }
}

풀이는 주어진 solve 메서드에 작성하면 된다.

 

Solution :

1. jewels의 각 char를 중복없이 Set에 저장한다.
2. stones의 각 char를 돌며 jewels에 해당하는 char가 있는지 센다.

import java.util.HashSet;
import java.util.Set;

public class JewelsAndStones {

    // time complexity : for loop -> O(n)
    // space complexity : jewelSet (chars of jewels) -> O(n)
    public int solve(String jewels, String stones) {

        // each char without duplicates
        Set<Character> jewelSet = new HashSet<>();
        for(char c : jewels.toCharArray()){
            jewelSet.add(c);
        }

        // compare and count
        int cnt = 0;
        for(char s : stones.toCharArray()){
            if(jewelSet.contains(s)) cnt++;
        }

        return cnt;
    }
}

 

Complexity :

• 시간복잡도 (Time Complexity)
  • 주어진 문자열 길이만큼 for문 반복에 따라 O(n)
• 공간복잡도 (Space Complexity)
  • jewels의 각 char를 담는 Set 사용에 따라 O(n)

 

Sample(Test) :

import java.util.HashSet;
import java.util.Set;

public class JewelsAndStones {

    // time complexity : for loop -> O(n)
    // space complexity : jewelSet (chars        of jewels) -> O(n)
    public int solve(String jewels, String stones) {

        // each char without duplicates
        Set<Character> jewelSet = new HashSet<>();
        for(char c : jewels.toCharArray()){
            jewelSet.add(c);
        }

        // compare and count
        int cnt = 0;
        for(char s : stones.toCharArray()){
            if(jewelSet.contains(s)) cnt++;
        }

        return cnt;
    }

    public static void main(String[] args){
        String jew = "aA";
        String stone = "aAAbbb";

        JewelsAndStones j = new JewelsAndStones();
        System.out.println(j.solve(jew, stone));
    }
}

 

위 테스트 코드를 실행한 결과는 다음과 같다.

3