[ Top Interview 150 ] 383. Ransom Note

문제

383. Ransom Note

Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise.

Each letter in magazine can only be used once in ransomNote.

• Input : 두 문자열 ransomNote, magazine
• Output : magazine의 문자열을 조합하여 ransomNote를 만들 수 있는가?
  • magazine의 특정 문자를 중복하여 사용할 수 없다.

알고리즘 전략

• 전략 1. Map 자료구조 사용

  • ['문자' - '나온 횟수'] 로 구성된 Map을 이용
  • magazine을 Map으로 만든 후에 ransomNote의 문자로 '나온 횟수'를 1씩 차감하는 방법을 이용
  • Time complexity : O(n)
  • Space complexity: O(n)

• 전략 2. Sorting

  • 두 문자열을 Sorting 하고 각각의 index를 설정하여 ransomNote의 모든 문자가 magazine안에 있는지 확인
  • Time complexity : O(nlogn)
  • Space complexity: O(n)

답안 1

• Map 자료구조 이용
  • Time complexity : O(n)
  • Space complexity: O(n)

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

        for (int i = 0; i < magazine.length(); i++) {
            char letter = magazine.charAt(i);
            int count = countOfLetter.getOrDefault(letter, 0);
            countOfLetter.put(letter, count + 1);
        }
        
        for (int i = 0 ; i < ransomNote.length(); i++) {
            char letter = ransomNote.charAt(i);
            int count = countOfLetter.getOrDefault(letter, 0);
            if (count <= 0) {
                return false;
            }
            countOfLetter.put(letter, count - 1);
        }
        
        return true;
    }
}

답안 2

• Sorting 이용 (Java 제공 라이브러리 사용)
  • Time complexity : O(nlogn)
  • Space complexity: O(n)

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        
        char[] magazineArray = magazine.toCharArray();
        char[] noteArray = ransomNote.toCharArray();

        Arrays.sort(magazineArray);
        Arrays.sort(noteArray);

        int noteIndex = 0;
        int magazineIndex = 0;
        while (noteIndex < noteArray.length && magazineIndex < magazineArray.length) {
            if (noteArray[noteIndex] < magazineArray[magazineIndex]) {
                return false;
            } else if (noteArray[noteIndex] == magazineArray[magazineIndex]) {
                noteIndex++;
            }
            magazineIndex++;
        }

        return noteIndex == noteArray.length;
    }
}

답안 비교

• 기본적으로 Time complexity는 Map을 사용하는 방법이 더 좋음
  • 그럼에도 Sorting이 시간 성능이 더 잘 나오는 것은 제공되는 데이터의 길이가 그렇게 길지 않은 것으로 추정됨
    • 1 <= ransomNote.length, magazine.length <= 100,000
  • Map을 만들고 쓰는 데에 생각보다 비용이 많이 필요로 하는 것을 알 수 있었다.