본문 바로가기

Leetcode

[Leetcode] 383. Ransom Note - JS

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

 

 

1. 문제 분석

문제분석
--------------------
- ransomNote, magazine 두 문자열이 주어진다.
- magazine으로 ransomNote가 구성될 수 있으면 true, 그렇지 않으면 false를 반환하라.
- magazine에 있는 각 문자는 ransomNote에 한번씩만 사용될 수 있다.

제한조건
--------------------
- 1 <= ransomNote.length, magazine.length <= 10^5
- ransomNote, magazine은 영어 소문자로 구성된다.

 

2. 접근 방법

접근방법
--------------------
magazine 의 hashMap을 만들어 갯수를 카운팅한다.
ransomNote를 순회하여 hashMap에서 없으면 false를 반환한다.

 

 

3. 코드

var canConstruct = function(ransomNote, magazine) {
    const hash = {};
    for (let letter of magazine) {
        hash[letter] = (hash[letter] || 0) + 1
    }
    
    for (let letter of ransomNote) {
        if (hash[letter]) {
            hash[letter]--;
        } else {
            return false;
        }
    }
    return true;
};

 

 

 

4. 복잡도 분석

- 시간복잡도: O(m+n), m == magazine.length, n == ransomNote.length

- 공간복잡도: O(1)

 

 

hashMap을 사용하여 magazine의 문자열의 갯수보다 ransomNote 문자열이 적거나 존재 하지 않는다면 false를 반환하고,

해당 반복문이 종료될 때 까지 false를 반환하지 않았다면 true를 반환한다.

'Leetcode' 카테고리의 다른 글

[Leetcode] 290. Word Pattern - JS  (0) 2024.10.17
[Leetcode] 205. Isomorphic Strings - JS  (0) 2024.10.16
[Leetcode] 289. Game of Life - JS  (0) 2024.10.14
[Leetcode] 73. Set Matrix Zeroes - JS  (0) 2024.10.12
[Leetcode] 48. Rotate Image - JS  (3) 2024.10.11