Ransom Note

주어진 두 문자열에 대해 (ransomNote, magazine)
magazine을 구성하는 문자들로 ransomNote 문자열을 구성할 수 있는지 없는지를
판단한다.

magazine을 구성하는 문자열을
HashMap으로 변환한다. (개별문자를 key 로, 그 갯수를 value)

그 다음, ransomNote 문자열을 순환하면서 그 문자가 magazine에 존재하는지 존재하지 않는지
체크 후, 존재한다면 그 갯수를 -1 을 한다. 그렇게 진행하여 문자를 구성할 수 있다면, true
없다면 false 반환한다.

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<String,Integer> magazineMap = convertMagazineToMap(magazine);

        for(int i = 0; i < ransomNote.length(); i++){
            String ch = String.valueOf(ransomNote.charAt(i));
            if(magazineMap.get(ch) != null && magazineMap.get(ch) > 0){
                magazineMap.put(ch, magazineMap.get(ch) - 1);
                continue;
            }else {
                return false;
            }
        }
        return true;
    }

    private Map<String, Integer> convertMagazineToMap(String magazine){
        Map<String,Integer> magazineMap = new HashMap<>();
        for(int i = 0; i < magazine.length(); i++){
            String ch = String.valueOf(magazine.charAt(i));

            if(!magazineMap.containsKey(ch)){
                magazineMap.putIfAbsent(ch,1);
                continue;
            }
            magazineMap.put(ch,magazineMap.get(ch)+1);
        }
        return magazineMap;
    }
}

다른 풀이 :
HashMap 구조를 사용하라는 지문과 달리, 메모리 및 속도에서 우위를 가져오도록한 풀이이다.
indexOf(주어진 문자가 주어진 숫자의 인덱스로부터 시작하여 몇번째 인덱스에 위치하는지 찾는)
함수를 사용했다.

예를 들어
ransomNote 가 aazbz 이고, magazine 이 aazhhbhhhz 일때
arr는 [2,6,0,0,0,0,0,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,10] 로 구성되는데
arr의 각인덱스는 a-z를 의미하고, 각원소의 값은
magazine 문자열에서 각 알파벳이 발견된 특정 인덱스를 의미한다.
(a는 2, b는 6, z는 10)

다시 예를 살짝바꿔 ransomNote 가 aazbz 이고, magazine 이 aahhbhhhz 일때
ransomNote 에는 z가 두개, magazine에는 z가 하나이다.
최종으로 발견된 z의 인덱스는 9이고 다음z는 발견될 수 없다.
따라서 indexOf(z,9)로부터 -1을 반환받고 이는
magazine 문자열에 해당 알파벳이 없다는 뜻이니,
ransomNote문자열을 구성할 수 없다고 최종적으로 판단할 수 있다.

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (magazine.length() < ransomNote.length()) 
            return false;
        int[] arr = new int[32]; // -97
        for(int i=0; i<ransomNote.length(); i++) {
            char c = ransomNote.charAt(i);
            int val = magazine.indexOf(c, arr[c-'a']);
            if (val == -1) return false;
            arr[c-'a'] = val+1;
        }
        return true;

    }
}