🏷️383. Ransom Note

---

1. 문제 설명

• 두 개의 문자열 ransomNote와 magazine이 주어지면, magazine의 문자를 사용하여 ransomNote를 구성할 수 있는 경우 true를 반환하고 그렇지 않으면 false를 반환합니다.
• 매거진의 각 글자는 ransomNote에서 한 번만 사용될 수 있습니다.

---

2. 접근 방법

• 먼저 HashMap으로 문자열 magazine의 문자들을 반복문을 통해 map에 저장합니다.
• 저장하면서 map의 key값이 없는 경우 default값을 추가하고, 있을 경우 해당 key의 value값을 +1 하여 중복된 key값을 count합니다.
• 문자열 ransomNote의 문자를 조회하는 반복문을 통해 초기화한 map의 key에 있는지, 그리고 해당 key의 value값이 0 이상인지 조건문을 통해 확인합니다.
• ture면 해당 key의 value값을 -1하여 count를 줄이고, false면 false을 반환합니다.
• 반복문을 다 돌면 해당 문자들이 전부 존재한다는 뜻이므로 true를 반환합니다.

---

3. 구현 코드

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        
        Map<Character, Integer> map = new HashMap();
        
        // magazine 문자 map에 초기화
        for(char c : magazine.toCharArray())
            map.put(c, map.getOrDefault(c, 0) + 1);
        
        // ransomNote 문자 존재 및 개수 확인
        for(char c : ransomNote.toCharArray()){
            if(map.containsKey(c) && map.get(c) > 0)
                map.put(c, map.get(c) - 1);
            else
                return false;
        }
        
        return true;
        
    }
}

• 시간 복잡도 : O(n)
• 공간 복잡도 : O(1)
  • 최악의 경우 HashMap의 공간 복잡도는 O(n)이지만 여기는 문자열에 있는 알파벳만 사용하며 그 개수가 제한되어 있습니다. 그래서 O(1)의 공간 복잡도를 가진다고 볼 수 있을 것 같습니다.

---

4. 개선 사항

HashMap을 사용하지 않고 정해지 알파벳 26개만큼 배열을 만들어 HashMap과 비슷한 기능을 하게 만들었습니다.

• 알파벳 수만큼 배열을 만들고 문자열 magazine을 문자를 반복문으로 조회하여 배열에 문자 수를 저장합니다.
• 이때 문자 a의 아스키코드값은 97이므로 a~z까지 magazine.charAt(i) - 'a'을 하면 배열에 index 0~25을 가리키는 값으로 사용될 수 있습니다.
• 그리고 나서 반복문을 통해 문자열 ransomNote의 문자와 같은 문자가 있는지 비교를 합니다.

public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        // 알파벳 수만큼 배열 할당
        int[] arr = new int[26];
        
        // 문자열 magazine을 문자로 배열 초기화
        for (int i = 0; i < magazine.length(); i++) {
            arr[magazine.charAt(i) - 'a']++;
        }
        
        // 같은 문자 확인 
        for (int i = 0; i < ransomNote.length(); i++) {
            if(--arr[ransomNote.charAt(i)-'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

---

5. 최종 회고

• 이전에 푼 문제와 비슷한 문제로 다시 HashMap를 활용하면서 연습할 수 있어 재밌었습니다.
• 다른 코드를 보며 배열을 HashMap 처럼 사용할 수 있는 방법을 알게되어 신기했습니다. 다음에는 값의 범위가 작은 문제라면 배열을 사용하는 생각을 해보면 좋을 것 같습니다.