[Dart] 383. Ransom Note

1. 문제

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

 

 

 

2. 요구사항

1) 두 문자열 ransomNote와 magazine이 주어진다.

2) ransomNote를 작성하기 위해 필요한 모든 문자를 magazine에서 가져올 수 있는지 확인한다.

3) 각 문자는 magazine에서 단 한 번만 사용할 수 있다.

4) ransomNote와 magazine은 영어 소문자로 구성된다.

 

 

 

3. 핵심 아이디어

1) magazine의 알파벳 등장 횟수 저장 후, ransomNote에 알파벳이 등장하면 횟수 감소

magazine의 알파벳 등장 횟수를 List <int> 타입의 charCount 변수에 저장한다.

 

ransomNote가 필요한 알파벳을 magazine에서 만들 수 있는지 확인한다.

ransomNote를 한 글자씩 순회하면서 그 문자가 charCount에 남아있는지 확인한다.

 

만약, 문제가 없다면 true를 반환한다.

 

 

 

 

2) 코드

class Solution {
  bool canConstruct(String ransomNote, String magazine) {
    // 26개 크기의 리스트에 0 저장
    // 각 알파벳이 magazine에 몇 번 나왔는지 저장
    List<int> charCount = List.filled(26, 0);

    for(int i = 0; i< magazine.length; i++) {
        // charCount에 magazine의 알파벳 등장 횟수 저장
        // charCount의 index는 알파벳 순서
        charCount[magazine.codeUnitAt(i) - 'a'.codeUnitAt(0)]++;
    }

    for(int i = 0; i < ransomNote.length; i++) {
        // ransomNote에서 필요한 문자의 알파벳 순서 계산
        int index = ransomNote.codeUnitAt(i) - 'a'.codeUnitAt(0);
        
        // 문자가 magazine에 없다면 false 반환
        if(charCount[index] == 0) return false;

        // magazine의 알파벳 등장 횟수 1 감소
        charCount[index]--;
    }
    return true;
  }
}