[LeetCode] 383. Ransom Note

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

Ransom Note - LeetCode

문제 유형 : 해시맵

문제 난이도 : Easy

 

문제

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.

 

두 문자열 ransomNote와 magazine이 주어집니다. 만약 magazine의 알파벳들로 ransomNote를 완성시킬 수 없다면, false를, 가능하다면 true를 반환하시오.

magazine의 각 철자는 ransomNote에 한 번씩만 쓰일 수 있습니다(a 하나도 aa를 만들 수 없습니다)

 

풀이

<알파벳, 개수>로 해시맵을 만들어서 magazine을 탐색하며 각 알파벳에 해당하는 개수를 늘립니다.

ransomNote를 탐색하며 개수를 하나씩 줄입니다. 개수가 음수가 되면 바로 false를 반환하고, ransomNote를 무사히 탐색했다면 true를 반환합니다.

 

코드(C++)

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> m;

        for(int i = 0; i < magazine.size(); i++){
            m[magazine[i]]++;
         }

        for(int i = 0; i < ransomNote.size(); i++){
            m[ransomNote[i]]--;
            if(m[ransomNote[i]] < 0){
                return false;
            }
         }
        return true;
    }
};