[Leetcode Top Interview 150] 383. Ransom Note

난이도 : easy

문제링크

• 두개의 문자열이 주어진다 : ransomNote, magazine
• magazine의 문자를 사용해 ransomNote를 생성할 수 있다면 true를 리턴하라

 

1. 접근법

• magazine이 ransomNote의 모든 문자를 포함해야 함
• magazine의 문자 별 갯수를 hashtable을 사용하여 관리한다
• ransomNote의 문자들을 각각 순회하면서
  • megazine의 문자에 포함되어 있는지 확인한다
  • 확인될 경우, 해당 문자를 사용하여 ransomNote를 생성하는데 쓴다
    • Key의 value값을 내린다

 

3. 구현 코드

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

        for (char c : magazine.toCharArray()) {
            if (map.containsKey(c)) {
                map.put(c, map.get(c)+1);
            } else {
                map.put(c, 1);
            }
        }

        for (char c : ransomNote.toCharArray()) {
            if (!map.containsKey(c)) {
                return false;
            } else {
                if (map.get(c) == 0) {
                    return false;
                }

                map.put(c, map.get(c)-1);
            }
        }

        return true;
    }
}

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - 모든 데이터를 순회함
• 공간복잡도 : O(n) - 모든 데이터를 생성해야 함