문제

두 개의 문자열 ransomNote와 magazine이 주어진다. magazine에 사용된 문자들로 ransomeNote 문자열을 만들 수 있으면 true, 만들 수 없으면 false를 리턴하는 문제이다.

첫번째 풀이

가장 쉬운 풀이는 magazine에 쓰인 문자들의 개수를 파악한뒤 ransomNote에 쓰인 각 문자의 개수가 magazine에 쓰인 개수보다 많으면 false를 리턴하는 것이다. 문자의 개수를 세기위해 HashMap 자료구조를 활용해 문자를 key로, 쓰인 개수를 value로 저장한다.

이 풀이의 시간복잡도는 $O(n)$를 갖는다. 문자는 영어 소문자로 한정되어 있기 때문에 문자열의 길이가 늘어나도 HashMap에 최대 26개만 저장된다. 따라서 공간복잡도는 $O(1)$을 갖는다.

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> letters = new HashMap<>();
        for (char ch : magazine.toCharArray()) {
            letters.put(ch, letters.getOrDefault(ch, 0) + 1);
        }

        for (char ch : ransomNote.toCharArray()) {
            int useCount = letters.getOrDefault(ch, 0);
            if (useCount == 0) {
                return false;
            }

            letters.replace(ch, useCount - 1);
        }

        return true;
    }
}

두번째 풀이

문제의 카테고리는 HashMap이지만 사실 HashMap의 key를 int로 표현할 수 있으면 배열로도 해결할 수 있다. 또한 배열로 풀이하는 것이 메모리에 접근하는데 더 빠르기 때문에 HashMap을 사용해 풀이하는 것보다 더 빠른 성능을 기대할 수 있다.

이 문제에서 각 문자열을 이루는 문자들은 모두 소문자 알파벳이다. 소문자 알파벳은 총 26자로 배열의 인덱스로 표현할 수 있다. 각 문자에서 a의 10진수 아스키 코드값을 빼면 소문자 알파벳을 0 ~ 25까지로 표현할 수 있기 때문이다. 이를 활용해 각 문자의 사용 횟수를 배열로 관리해 풀이할 수 있다.

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        char[] letters = new char[26];
        for (char ch : magazine.toCharArray()) {
            letters[ch - 'a']++;
        }

        for (char ch : ransomNote.toCharArray()) {
            int idx = ch - 'a';
            if (letters[idx] == 0) {
                return false;
            }

            letters[idx]--;
        }

        return true;
    }
}

동일한 시간복잡도와 공간복잡도를 갖지만 확실히 HashMap을 사용하는 것보다 배열로 해결하는 것이 더 빠르며 메모리 또한 적게 사용한다.