[2주차] 383. Ransom Note

https://leetcode.com/problems/ransom-note/?envType=study-plan-v2&envId=top-interview-150 

Ransom Note - LeetCode

---

📝 문제

두 개의 문자열 ransomNote 와 magazine 이 주어진다. magazine 문자열의 각 문자로 ransomNote 를 구성할 수 있으면 true, 없으면 false 를 리턴하라. 단, 각 문자는 한 번씩만 사용 가능하다.

 

🎈 풀이

HashMap 을 이용하여서 각 문자가 나온 횟수를 기록하였다.

시간복잡도: O(n)

공간복잡도: O(n)

public boolean canConstruct(String ransomNote, String magazine) {
    HashMap<Character, Integer> map = new HashMap<>();
    for (int i=0; i<magazine.length(); i++) {
        char c = magazine.charAt(i);
        int prev = map.getOrDefault(c, 0);
        map.put(c, prev + 1);
    }

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

    return true;
}

• HashMap의 Key는 문자, Value는 해당 문자가 나온 횟수를 의미한다.
• 3행: magazine 문자열을 순회하며 각 문자가 나올 때 마다 카운트를 늘리며 map에 기록한다.
• 9행: ransomNote 문자를 순회하며, 현재 문자가 map에 없거나 value가 0 이하면  magazine 문자열로 구성할 수 없음을 의미하므로 false를 리턴한다.
• ransomNote 문자열을 순회 완료하였다면 true이다.

 

📈 타 솔루션 참고

로직은 나와 동일하나 HashMap 을 사용하는 대신 배열을 사용하였다.

시간복잡도: O(n)

공간복잡도: O(n)

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;
}

기본적으로 객체 구조를 선언하는 데에는 메모리 비용이 들어가고, 원시타입을 Collection 에 담을 수 없기 때문에 Boxing, Unboxing 과정이 추가로 필요하다. 따라서 HashMap 을 사용한 코드보다 효율적이다.