[ch5 효율성(투포인터 알고리즘, 슬라이딩윈도우, 해쉬)] 아나그램 javascript

해당 포스팅은 인프런의 "자바스크립트 알고리즘 문제풀이" 강의 중 챕터5의 아나그램 문제 풀이를 다룬다. Hash Map으로 풀이하였다.

문제

문제 추론

주어진 두 개의 단어가 아나그램이기 위해서는 두 단어의 키밸류쌍이 동일해야 한다. 문제에서 두 단어의 길이가 같다고 명시되어 있으므로, 단어A를 해쉬로 만든 후 다른 한 단어 B를 순회하면서 value를 제거하는 식으로 풀 수 있다. B의 현재 요소가 A에 존재하지 않거나(key 존재 x) value가 0일 시에는(현재 요소가 A보다 B가 더 많음) 아나그램이 될 수 없으므로 NO를 출력한다.

Pseudocode

function solution(str1, str2) {
	str1을 해쉬로 만든다.
    for (x of str2) {
    	if (map1에 키 x가 없음 or map의 키 x의 value가 0 이하) {
        	then return "NO"
        }
        map1의 키 x의 value를 1 줄여준다.
    }
  	return "YES";
}

전체 코드

function mapStr(str) {
    const map = new Map();
    for (let x of str) {
        if (map.has(x)) {
            map.set(x, map.get(x)+1);
            continue;
        }
        map.set(x, 1);
    }
    return map;
}

function solution(s1, s2) {
    const map1 = mapStr(s1);
    for (let x of s2) {
        if (!map1.has(x) || map1.get(x) === 0) {
            return "NO";
        }
        map1.set(x, map1.get(x) - 1);
    }
    return "YES";
}

const s1 = 'abaCC';
const s2 = 'Caaab';
console.log(solution(s1, s2));