[LeetCode] 383. Ransom Note - Java

Ransom Note - LeetCode

 

문제

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

 

Example 1:

Input: ransomNote = "a", magazine = "b"
Output: false

Example 2:

Input: ransomNote = "aa", magazine = "ab"
Output: false

Example 3:

Input: ransomNote = "aa", magazine = "aab"
Output: true

 

Constraints:

• 1 <= ransomNote.length, magazine.length <= 105
• ransomNote and magazine consist of lowercase English letters.

 

두 문자열 ransomNote 와 magazine 이 주어졌을 때 magazine 의 문자들로 ransomNote 를 구성할 수 있으면 true, 불가능하면 false를 반환한다.

 

---

 

내 풀이

HashMap 사용

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> map = new HashMap<>();

        for(int i=0; i<magazine.length(); i++){ 
            char c = magazine.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        for(int i=0; i<ransomNote.length(); i++){
            char c = ransomNote.charAt(i);
            if(map.containsKey(c) && map.get(c) > 0){
                 map.put(c, map.get(c)-1);
            } else {
                return false;
            }
        }
        return true;

    }
}

 

1. magazine 문자열을 순회하며 구성하는 문자의 빈도를 value로 맵에 저장한다.
2. ransomNote 문자열을 순회하며
   • 맵이 현재 문자를 키값으로 가지고 있는지, value 즉 빈도수가 0 이상인지 확인하고 그렇다면 빈도수를 1 감소시킨다.
   • 만약 조건을 만족하지 못한다면 ransomNote을 만들 수 없으므로 false를 반환한다.
3. 반복문이 끝나면 ransomNote 을 만들 수 있다는 뜻이므로 true를 반환한다.

 

• 시간복잡도 : O(m + n) = O(n) - 문자열 순회
• 공간복잡도 : O(n) - 해시 맵의 크기에 비례

 

---

 

다른 사람의 풀이

해시맵을 사용하지 않는 풀이도 있어서 찾아봤다.

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) return false;
        int[] alphabets_counter = new int[26];

        for (char c : magazine.toCharArray())
            alphabets_counter[c-'a']++;

        for (char c : ransomNote.toCharArray()){
            if (alphabets_counter[c-'a'] == 0) return false;
            alphabets_counter[c-'a']--;
        }
        return true;
    }
}

 

여기선 각 문자의 빈도를 배열에 저장한다.

문자열이 알파벳 소문자로만 구성되어있다는 조건을 이용한 풀이이다.

각 문자들을 길이가 26인 배열에 모두 저장할 수 있고, 각 문자 c에 대해 c - 'a'를 인덱스로 사용하면서 빈도를 증가시킨다.

길이가 상수인 배열을 사용했기 때문에 공간복잡도는 O(1)로 줄어든다.

 

내 원래 풀이와 비교해보니 효율이 대폭 개선되었다.

 

항상 복잡도를 줄일 수 있는 방향이 있는지 한 번 더 생각해보는 것이 중요하다.