[LeetCode] 383. Ransom Note

Ransom Note - LeetCode

두 문자열 ransomNote와 magazine이 주어졌을 때, magazine의 문자를 사용하여 ransomNote를 구성할 수 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.

magazine의 각 문자는 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

 

 

문제접근

해시맵을 사용해서 풀고자 하였습니다.

해시의 메서드들은 O(1)의 시간복잡도를 갖고있기 때문에 공간복잡도를 어느정도 포기하고

시간복잡도면에서 좋은코드를 작성할 수 있습니다.

 

magazine의 각 문자를 map에 카운팅하고

ransomNote를 확인하면서 map에 값이 0이 아니라면 true

하나라도 0이 있다면 false를 반환하도록 하였습니다.

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

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

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

 

시간복잡도

O(n)의 시간복잡도가 필요합니다.

 

다른사람의 풀이

배열을 map처럼 사용한 풀이입니다.

    public boolean canConstruct(String ransomNote, String magazine) {
        int[] charCounts = new int[26]; // Assuming lowercase English letters
        
        for (char c : magazine.toCharArray()) {
            charCounts[c - 'a']++;
        }

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

 

느낀점

해시맵을 사용하는 이유는 분명합니다.

조회, 삽입, 삭제가 O(1) 이라는 아주 효율적인 자료구조입니다.

반면 공간복잡도는 그만큼 잡아먹는다는것을 꼭 기억해야합니다.

 

참고

https://leetcode.com/problems/ransom-note/solutions/3973539/three-simple-java-solutions-runtime-2ms-beats100/?envType=study-plan-v2&envId=top-interview-150