May LeetCoding Challenge[Day3] - Ransom Note

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.
Each letter in the magazine string can only be used once in your ransom note.

Note:You may assume that both strings contain only lowercase letters.

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

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

 

 - 자료구조를 먼저 생각하게 되었다.

 - Map을 사용하고, Map을 통해서 카운팅을 하면 되지 않을까 생각했었다.

 - 그렇게 했을 때, HashMap을 2개 만들면서, O(N)이 2번 발생하고, HashMap을 다시 Search할 때, O(N)이 1번 발생했다.

 

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

 

 - 더 좋은 방법은 없을까?

 

3. 내가 작성한 알고리즘

 

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        char[] ransomArray = ransomNote.toCharArray();
        char[] magazineArray = magazine.toCharArray();
        Map<Character,Integer> ransomMap = makeMap(ransomArray);
        Map<Character,Integer> magazineMap = makeMap(magazineArray);
        boolean answer = true;
        //O(N)
        for(Map.Entry<Character,Integer> ransomEntry : ransomMap.entrySet()){
            Character key = ransomEntry.getKey();
            if(magazineMap.containsKey(key)){//O(1)
                Integer value = ransomEntry.getValue();

                if(magazineMap.get(key) < value){
                    answer = false;
                    break;
                }
            }else{
                answer = false;
                break;
            }
        }
        //result : O(3N)
        return answer;
    }
    
    //O(2N)
    private Map<Character, Integer> makeMap(char[] array){
        Map<Character, Integer> map = new HashMap();
        for(char ransom : array){
            if(map.containsKey(ransom)){
                map.put(ransom, map.get(ransom) + 1);
            }else{
                map.put(ransom, 1);
            }
        }
        return map;
    }
}

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

앞에 장대 그래프가 있다...

 

5. 내가 작성한 알고리즘 보완하기

 

 - 이전에 작성한 알고리즘에서 makeMap() 메소드를 ransom과 magzine 두 배열에 대해서 모두, 만들어준 것에 대해서 고민을 했었다.

 - ransomNote의 경우에는 for문으로 돌리고, magazine에서 contains를 통해서 탐색을 할 때, 문제가 성립된다는 것을 생각하게 되었다.

 - 따라서 ransomNote는 단순히 for문을 돌리는 용도이기 때문에 array로 남겨놓고, 나머지 magazine에 대한 부분만 Map을 사용하기로 결정했다.

 

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        char[] ransomArray = ransomNote.toCharArray();
        char[] magazineArray = magazine.toCharArray();
        Map<Character,Integer> magzineMap = makeMap(magazineArray);
        boolean answer = true;
        
        //O(N)
        for(int i=0; i< ransomArray.length; i++){
            Character key = ransomArray[i];
            Integer value = magzineMap.get(key);
            if(value != null && value > 0){
                magzineMap.put(key, value-1);
            }else{
                answer = false;
                break;
            }
        }
        //result : O(2N)
        return answer;
    }
    
    //O(N)
    private Map<Character, Integer> makeMap(char[] array){
        Map<Character, Integer> map = new HashMap();
        for(int i=0; i<array.length; i++){
            if(map.containsKey(array[i])){
                map.put(array[i], map.get(array[i]) + 1);
            }else{
                map.put(array[i], 1);
            }   
        }
        return map;
    }
}

 

6. 다른 사람이 작성한 알고리즘을 보고 배운점

 

똑같다 ㅋㅋ

7. 내가 작성한 알고리즘을 보완하고 또 보완하기

 

 - Map이라는 자료구조를 사용함에 따라서, 공간복잡도가 괜히 많을 것 같고, 속도도 어딘가에서 느리지 않을까 계속 고민을 했었다. 이러한 문제를 풀 때는 우선, 자료구조를 선택하고, 해당 문제를 자료구조로 써서 정답을 찾아낸 후에, Array로 변경시 속도적인 측면에서 많은 득이 된다.

 - 따라서, Map을 Array로 변경시켜 줄 것이다.

 

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        char[] ransomArray = ransomNote.toCharArray();
        char[] magazineArray = magazine.toCharArray();
        int[] magzineMap = makeArrayMap(magazineArray);
        boolean answer = true;
        
        //O(N)
        for(int i=0; i< ransomArray.length; i++){
            char key = ransomArray[i];
            int value = magzineMap[(int)key];
            if(value > 0){
                magzineMap[(int)key] = magzineMap[(int)key] - 1;
            }else{
                answer = false;
                break;
            }
        }
        //result : O(2N)
        return answer;
    }
    
    //O(N)
    private int[] makeArrayMap(char[] inputs){
        int[] arrayMap = new int[150];
        for(int i=0; i<inputs.length; i++){
            arrayMap[(int)inputs[i]] = arrayMap[(int)inputs[i]] + 1;
        }
        return arrayMap;
    }
}

 

8. 짝짝짝 결과

 

 속도 측면에서 정말 빨라진 것을 발견할 수 있었다. 그렇지만 시간 복잡도는 모두 O(2N)이다.

 추측해볼 수 있는 것은 Map은 Array에 비해서 정말 느리다.

 

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

Explore - LeetCode