[LeetCode/Top Interview 150] [Hash Table] 383. Ransom Note

문제 링크: https://leetcode.com/problems/ransom-note/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: easy

문제:

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 <= 10^5
ransomNote and magazine consist of lowercase English letters.

전략:

magazine의 문자는 ransomNote를 만드는데 각 1번씩 사용 가능.
기본 true를 리턴하고 false인 경우 즉시 리턴하도록 구현해야겠다.
먼저 magazine의 알파벳을 집계하여 저장하고, ransomNote를 순회하며 해당 위치 알파벳의 값을 감소시키다 음수값이 나오면 false 리턴.

코드 구현:

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        char[] rn = ransomNote.toCharArray();
        char[] mg = magazine.toCharArray();
        for (int i=0;i<mg.length;i++) {
            map.put(mg[i], map.getOrDefault(mg[i],-1)+1);
        }
        for (int i=0;i<rn.length;i++) {
            if (!map.containsKey(rn[i])) return false;
            int cnt = map.put(rn[i], map.getOrDefault(rn[i],0)-1);
            if (cnt < 0) return false;
        }
        return true;
    }
}
Time: 14 ms (49.72%), Space: 44.1 MB (50.05%) - LeetHub

실행결과:
https://github.com/1-vL/LeetCode/blob/main/0383-ransom-note/0383-ransom-note.java

개선 방안:

HashMap 대신 알파벳 26자리의 숫자를 저장하는 int[] 사용하여 집계

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] alpha = new int[26];
        char[] mg = magazine.toCharArray();
        char[] rn = ransomNote.toCharArray();
        
        // magazine의 알파벳 집계
        for (int i=0;i<mg.length;i++) {
            alpha[mg[i] - 'a']++;
        }

        // ransomNote 만드는데 사용한 경우 제거
        for (int i=0;i<rn.length;i++) {
            if (--alpha[rn[i] - 'a'] < 0) return false;
            // 사용한 후 음수값이 되면 즉시 false 리턴
        }
        return true;
    }
}
Time: 1 ms (99.82%), Space: 43.14MB (99.32%) - LeetHub

Solutions 탭의 타인 코드:

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;
    }
}
 Time: 2 ms (95.82%), Space: 43.54MB (87.80%) - LeetHub

회고:

역시 사용할 수 있을만한 상황이라면 가장 단순한 자료 구조로 해결하는 것이 가장 효율적인 해결책이 되는 것 같다.