[LeetCode] 383. Ransom Note, Easy

1. 문제

• ransomeNote, magazine 두 문자열이 주어질 때, magazine의 각 문자로 ransomeNote 문자열을 만들 수 있으면 true, 아니면 false를 반환.
• magazine의 각 문자는 1 번만 쓰일 수 있다.
• 두 문자열에는 오로지 알파벳 소문자로 제한된다.

2. 해결

function canConstruct(ransomNote: string, magazine: string): boolean {
	// 1. a~z의 아스키코드 범위는 97 ~ 122이므로, 97을 뺀 0 ~ 25 인덱스 배열 생성.
    const countingArr = new Array(26).fill(0)    

	// 2. magazine 각 문자의 아스키코드 계산 후 해당 인덱스 값 증가.
    for(let i =0 ; i < magazine.length; i++ ) {
        countingArr[magazine.codePointAt(i) - 97] +=1;
    }


	// 3. ransomNote 각 문자를 돌면서 해당 문자의 인덱스에 값이 있는지 확인.
    for(let i =0 ; i < ransomNote.length; i++ ) {
    	// 4. 해당 문자에 해당하는 인덱스에 값이 없으면 불가능하므로 false 반환.
        if(countingArr[ransomNote.codePointAt(i) - 97] === 0) {
           return false
        }
        // 5. 각 인덱스 값을 감소.
        countingArr[ransomNote.codePointAt(i) - 97] -=1;
    }

    return true;
};

• 처음 접근은 문자열을 순회하면서, ransomeNote의 각 문자를 잘라가면서 찾아보려고 했는데 아스키 코드를 이용한 인덱싱 방법이 떠올라서 사용했다.

function canConstruct(ransomNote: string, magazine: string): boolean {

	// 1. Map 자료구조 생성.
    const map = new Map<String, number>()

	// 2. 각 문자를 key값으로 value 증가.
    for(const char of magazine) {
        let current = map.get(char) || 0;

        map.set(char, (map.get(char) || 0) + 1);
    }

	// 3. ransomNote 각 문자를 순회하며 해당 key의 value가 없으면 false.
    for(const char of ransomNote) {
        if(!map.get(char)) return false;

        map.set(char, map.get(char) - 1);
    }

    return true;
};

• 첫 번째로 풀어보고 Map 자료구조가 있다는게 생각이 나서 Map으로도 풀어봤는데, 더 오래 걸리더라.
• 이유는, Map은 해시 충돌의 경우가 있어서 평균 시간 복잡도가 O(n+m)이기 때문이다. 첫 번째는 O(n+m) 고정.
• Map을 쓰기 좋은 상황은 지금처럼 소문자 알파벳으로 제한되어 있는 경우 말고, 다양한 문자로 구성되어 있을 때 유용할 것 같다.