[알고리즘] 모든 아나그램 찾기(해쉬, 투포인터, 슬라이딩 윈도우)

문제

S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하 세요. 아나그램 판별시 대소문자가 구분됩니다. 부분문자열은 연속된 문자열이어야 합니다.

입력설명

첫 줄에 첫 번째 S문자열이 입력되고, 두 번째 줄에 T문자열이 입력됩니다. S문자열의 길이는 10,000을 넘지 않으며, T문자열은 S문자열보다 길이가 작거나 같습니다.

 

bacaAacba

abc

풀이

function compareMaps(map1,map2){
    // 두 map의 사이즈가 같은지 비교
    if(!map1.size === map2.size) return false;
    // 두 map의 key, value 값이 같은지 확인 
    for(let [key,val] of map1){
        if(!map2.has(key) || map2.get(key) !== val) return false;
    }
    return true;
}

function solution(s, t){
    let answer = 0;

    // 초기 슬라이딩 윈도우의 범위 (앞으로 하나씩 추가 & 삭제)
    const len = t.length -1;

    // 문자열 해시맵 생성
    let sH = new Map();
    let tH = new Map();
    for(let i = 0; i < len; i++){
        if(sH.has(s[i])) sH.set(s[i], sH.get(s[i])+1);
        else sH.set(s[i], 1);
    }
    for(x of t){
        if(tH.has(t)) tH.set(x, tH.get(x)+1);
        else tH.set(x, 1);
    }

    // 슬라이딩 윈도우 셋팅 (lt는 시작점, rt는 만들어진 map의 다음 범위부터 시작)
    let lt = 0;
    for(let rt = len; rt < s.length; rt++){
        // 해시맵에 새로운 범위 추가
        if(sH.has(s[rt])) sH.set(s[rt], sH.get(s[rt])+1);
        else sH.set(s[rt], 1);
        // tH와 sH가 같은지 비교
        if(compareMaps(sH, tH)) answer++;
        // lt와 rt를 한 칸씩 이동하여 새로운 범위 생성
        sH.set(s[lt], sH.get(s[lt])-1);
        if(sH.get(s[lt])===0) sH.delete(s[lt]);
        lt++;
    }
    return answer;
}

let a="bacaAacba";
let b="abc";
console.log(solution(a, b));