383. Ransom Note

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

문제

magazine에 있는 문자를 사용해, ransomNote를 구성할 수 있는지 확인하자.

• magazine과 ransomNote는 영문 소문자로 구성

입력

• 문자열 ransomNote, magazine

출력

• true/false

---

나의 풀이

접근

결국엔 ransomNote를 구성하는 글자가, ransomNote에 있는 글자의 개수만큼 magazine에 있는지를 찾는 문제이다.

따라서 HashMap에 그냥 ransomNote의 글자를 카운트해서 카운트 값과 글자를 넣어놓으면 되지 않을까? 라는 생각이 들었다.

구현 코드

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

        for (int i = 0; i < ransomNote.length(); i++) {
            Character c = ransomNote.charAt(i);
            map.put(c, map.containsKey(c) ? map.get(c) + 1 : 1);
        }

        for (int i = 0; i < magazine.length(); i++) {
            Character c = magazine.charAt(i);
            if (map.containsKey(c))
                map.put(c, map.get(c) - 1);
            if (map.get(c) != null && map.get(c).equals(0))
                map.remove(c);
        }

        return map.isEmpty();
    }
}

• (값, count) 이런 형태로 nums의 요소를 저장할 HashMap을 선언
• for문을 실행하며 ransomNote에 있는 문자 count → map에 저장
• magazine의 문자 for문 실행
  • 만약 map에 문자가 있다면, 해당 count -= 1
  • 만약 map의 요소 중 count가 0이라면 삭제
• map이 비어있다면, ransomNote의 문자를 magazine이 다 가지고 있었다는 의미이므로, map이 비어있는지를 return

결과

Time: O(n)

Space: O(n)

---

다른 풀이

이 풀이를 보고 아차 싶었다.

이 문제는 ransomNote와 magazine이 소문자로 구성된다는 조건이 실행 시간이 빠른 코드를 작성하는 데에 핵심이었다. 조건 하나가 코드의 실행 시간을 생각보다 크게 좌지우지할 수 있다는 것을 다시 한 번 깨달았다.

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] charCounts = new int[26];
        
        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;
    }
}

• 알파벳 숫자만큼의 int 배열을 선언한다.
• 그리고 magazine의 글자를 for문을 실행하면서 탐색한다
  • charCounts에 count값을 저장한다.
• ransomNote의 글자를 for문을 실행하며 탐색
  • charCounts의 해당 글자의 count값이 0보다 작거나 같다면 return false
  • 아니라면, charCounts의 해당 글자 count값 감소
• return true
  

사실 magazine과 ransomNote의 위치를 바꿔서 ransomNote의 글자의 count를 charCounts에 저장했다면 실행시간과 메모리 사용은 같지만, 가독성은 더 좋은 코드가 될 수 있었을 것 같다.

이렇게 이미 범위가 셀 수 있을 만큼의 작은 크기 (문제에서는 영어 소문자 → 지정범위)라면, 직접 그 범위를 명시한 후, 알고리즘을 진행하는 것도 하나의 방법이라는 점을 새기고 간다.