[자바 알고리즘 인터뷰] ch 11. 해시 테이블 (2) 보석과 돌

https://leetcode.com/problems/jewels-and-stones/description/

 

 

- J는 보석이며, S는 갖고 있는 돌이다. S에는 보석이 몇개나 있을까? 대소문자는 구분한다. 

 

 

풀이 1) 해시 테이블을 이용한 풀이 

 

- 갖고 있는 돌 stones의 엘리먼트 각각의 개수를 모두 헤아린 다음, jewels의 각 엘리먼트를 키로 하는 각각의 개수를 합산

- 먼저 freqs라는 해시 맵을 선언

Map<Character,Integer> freqs = new HashMap<>();

 

- 돌의 모음인 stones를 문자 단위로 하나씩 분리해 반복한다. 만약 처음 등장한 문자라면 1을 선언하고, 기존에 있던 문자라면 1을 더한다. 

//돌(S)의 빈도수 계산
for(char s : stones.toCharArray())
{
    //만약 이미 계산한 돌이면 기존 값+1
    if(freqs.containsKey(s))
        freqs.put(s,freqs.get(s)+1);
    //만약 처음보는 돌이면 1
    else
        freqs.put(s,1);
}

 

 

- 입력값 stones="aAAbbbb"는 해시맵 freqs에 다음과 같이 저장된다.

{
    a=1,
    A=2,
    b=4
}

 

 

- 이 중에서 보석을 나타내는 jewels의 문자를 꺼내어  해당 문자의 빈도수를 합하면 최종 결과가 된다. 

//보석(J)의 빈도수 합산
for(char j: jewels.toCharArray())
{
    //보석과 일치하는 돌의 개수를 합산 
    if(freqs.containsKey(j))
        count+=freqs.get(j);
}

 

 

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        int count = 0;
        Map<Character,Integer> freqs = new HashMap<>();

        //돌(S)의 빈도수 계산
        for(char s : stones.toCharArray())
        {
            //만약 이미 계산한 돌이면 기존 값+1
            if(freqs.containsKey(s))
                freqs.put(s,freqs.get(s)+1);
            //만약 처음보는 돌이면 1
            else
                freqs.put(s,1);
        }

        //보석(J)의 빈도수 합산
        for(char j: jewels.toCharArray())
        {
            //보석과 일치하는 돌의 개수를 합산 
            if(freqs.containsKey(j))
                count+=freqs.get(j);
        }

        return count;
    }
}

2밀리초

 

 

풀이 2) 해시셋을 이용한 풀이 

 

- HashSet은 집합(Set) 자료형으로, 집합의 특징을 그대로 갖고 있다.

- 즉, 엘리먼트를 중복해서 저장할 수 없고 각각의 값은 유일하다. 

 

- 보석 jewels를 추출해서 HashSet에 저장하고 돌 stones를 하나씩 비교하면서  저장했던 보석과 일치하면 개수를 하나씩 증가시킨다. 

 

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        int count = 0;
        Set<Character> freqs = new HashSet<>();

        //보석(jewels) 종류 저장
        for(char j : jewels.toCharArray())
            freqs.add(j);

        //돌이(stones)이 보석인 경우 +1
        for(char s : stones.toCharArray())
            if(freqs.contains(s)) count++;

        return count;
    }
}

1밀리초