LeetCode : 383. Ransom Note

문제 링크

문제 먼저 읽기

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

Input: ransomNote = "aa", magazine = "ab"
Output: false

어떻게 풀까?

생각

• HashMap을 사용해서 magazine 의 문자 개수를 더하고하고, ransomNote 문자를 순회하면서 HashMap에 저장된 문자 개수를 차감하여 magaziine의 모든 문자들로 ransomNote를 이룰 수 있는 지 확인해본다.
  • 이 방법으로 했을 때 O(2N)의 시간 복잡도가 들 것 같다.

수도코드

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> letters = new HashMap<>();
        
        for (char c : magazine.toCharArray()) {
            if (letters.get(c)==null) {
                letters.put(c, 1);
            } else {
                letters.put(c, letters.get(c)+1);
            }
        }
        
        for (char c : ransomNote.toCharArray()) {
            if (letters.get(c) == null) {
                return false;
            } else {
                letters.put(c, letters.get(c)-1);
                if (letters.get(c) < 0) return false;
            }
        }
        
        return true;
    }
}

결과

<aside> 💡 Success

Runtime: 18 ms, faster than 31.56% of Java online submissions for Ransom Note.

Memory Usage: 44.5 MB, less than 6.41% of Java online submissions for Ransom Note.

</aside>

2차 시도

• 공간 복잡도를 더 줄이기 위해서, 그리고 좀 더 효율적으로 해보기 위해 char[]로 바꿔볼 수 있을 것 같다.
  • 영어 소문자만 사용한다고 문제에 한정해 뒀기 때문에 가능한 방식이다. 공간 효율의 향상도 기대할 수 있을 것 같다.

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        char[] letters = new char['z'-'a'+1];
        
        for (char c : magazine.toCharArray()) {
            letters[c - 'a'] ++;
        }
        
        for (char c : ransomNote.toCharArray()) {
            if (letters[c - 'a'] <= 0) return false; // 처음 작성할 때 이부분의 순서를 잘못 썼었다. 로직에 주의하자.
            letters[c - 'a'] --;
        }
        
        return true;
    }
}

<aside> 💡 Success

Runtime: 2 ms, faster than 95.62% of Java online submissions for Ransom Note.

Memory Usage: 43 MB, less than 99.64% of Java online submissions for Ransom Note.

</aside>

다른 풀이 방식과 문제 회고

• 1 ms submission

class Solution {
    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;
    }
}

• 배열 생성시 수식을 사용하지 않고 ‘26’ 을 바로 입력하여 연산을 줄인 것 같다.