[ch5. 효율성(투포인터, 슬라이딩윈도우, 해쉬)] 모든 아나그램 javascript

해당 포스팅은 인프런의 "자바스크립트 알고리즘 문제풀이" 강의 중 챕터5의 모든 아나그램 문제 풀이를 다룬다. 해시, 투포인터, 슬라이딩 윈도우로 풀이하였다.

문제

문제 풀이

연속된 문자열이 아나그램인지를 판별하므로 슬라이딩 윈도우를 이용해야 한다. 그리고 주어진 T문자열이 연속된 문자열과 아날로그인지 판별하기 위해서는 정렬 후 문자열을 만들어서 판별하는 방법이 있겠지만, 슬라이딩 윈도우로 구현하면 loop를 돌면서 이전값을 빼고 현재 값을 더하는(투포인터 이용) 작업을 해주어야 하므로 HashMap으로 구현하는 것이 용이하다.

Pseudocode

문자열 t에 대해 HashMap 생성: tH
문자열 s에 대해 인덱스 0부터 t-1까지의 값을 HashMap 생성: sH

// 슬라이딩 윈도우 - O(N)
answer = 0;
시작 포인터 lt = 0;

for (끝 포인터 rt = t.len-1; rt < s.length; rt++) {
	rk = 끝 포인터 값 = s[rt];
  	if sH에 key rk가 있다면 then
    	sH의 key rk의 value + 1 해준다.
    else then
    	sH의 key rk의 value를 1로 세팅해준다.
    if 현재 tH가 sH와 같다면 then
    	아나그램이므로 answer + 1;
  	
  	lk = 시작 포인터 값 = s[lt];
  	sH의 key lk의 value - 1 해준다.
    if sH의 key lk의 value가 0이라면 then
    	sH에서 key lk를 삭제해준다.
    
    시작 포인터 lt + 1;
}

전체 코드

const s = 'bacaAacba';
const t = 'abc';
console.log(solution(s,t));

function solution(s, t) {
    const sH = new Map();
    const tH = new Map();
    const t_len = t.length - 1;
    
    // tH hashmap 생성
    for (let i=0; i<t.length; i++) {
        const el = t[i];
        if (tH.has(el)) {
            tH.set(el, tH.get(el)+1);
        } else {
            tH.set(el, 1);
        }
    }
    
    // sH 초기 hashmap 생성
    for (let i=0; i < t_len; i++) {
        const el = s[i];
        if (sH.has(el)) {
            sH.set(el, sH.get(el)+1);
        } else {
            sH.set(el, 1);
        }
    }
    
    // 슬라이딩 윈도우
    let answer = 0;
    let lt = 0;
    for (let rt = t_len; rt < s.length; rt++) {
        const rk = s[rt];
        if (sH.has(rk)) {
            sH.set(rk, sH.get(rk)+1);
        } else {
            sH.set(rk, 1)
        }
        if (compareMaps(sH, tH)) answer += 1;
        const lk = s[lt];
        sH.set(lk, sH.get(lk)-1);
        if (sH.get(lk) === 0) {
            sH.delete(lk);
        }
        lt += 1;
    }
    return answer;
}

// 두 Map이 일치하는지 판별
function compareMaps(map1, map2) {
    if(map1.size!==map2.size) return false;
    for(let [key, val] of map1){
        if(!map2.has(key) || map2.get(key)!==val) return false;
    }
    return true;
}