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

문제

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

입력설명

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

출력설명

S단어에 T문자열과 아나그램이 되는 부분문자열의 개수를 출력합니다.

입출력예제

입력
bacaAacba abc

출력
3

(출력설명: {bac}, {acb}, {cba} 3개의 부분문자열이 "abc"문자열과 아나그램입니다.)

문제 해결

const compareMaps = (map1, map2) => {
  // 두 map의 사이즈가 다르면 return false
  if (map1.size !== map2.size) return false;

  for (let [key, val] of map1) {
    // map1의 key값이 map2에 없거나
    // map2와 map1의 key값이 같지만, 두 개의 val이 다를 때 return false
    if (!map2.has(key) || map2.get(key) !== val) return false;
  }

  // 위의 조건을 다 만족하면 return true
  return true;
};

const solution = (S, T) => {
  let answer = 0;
  const [tHash, sHash] = [new Map(), new Map()];

  // 1. T문자열의 각 문자를 key로 가지는 map 객체 생성
  for (let x of T) {
    if (tHash.has(x)) tHash.set(x, tHash.get(x) + 1);
    else tHash.set(x, 1);
  }

  // 2. 슬라이딩 윈도우를 사용하기 위한 세팅. T문자열.legnth-1만큼의 S문자열의 각 문자를 key로 가지는 map 객체를 생성
  for (let i = 0; i < T.length - 1; i++) {
    if (sHash.has(S[i])) sHash.set(S[i], sHash.get(S[i]) + 1);
    else sHash.set(S[i], 1);
  }

  // 3. 투포인터 알고리즘을 위한 left 변수 선언 및 0으로 값 할당
  let left = 0;

  // 4. sHash를 세팅한 S문자열의 그 다음 key값 부터 슬라이딩 윈도우 만큼 다시 sHash map을 정의
  for (let right = T.length - 1; right < S.length; right++) {
    if (sHash.has(S[right])) sHash.set(S[right], sHash.get(S[right]) + 1);
    else sHash.set(S[right], 1);

    // 5. tHash와 sHash를 같은 사이즈로 만든 뒤, 비교 함수를 통해 true면 answer값 증가
    if (compareMaps(sHash, tHash)) answer++;

    // 6. 투포인터 알고리즘. left의 key값을 다시 -1해주고 만약 값이 0이라면 해당 key값을 삭제해 버리기(에러 방지)
    sHash.set(S[left], sHash.get(S[left]) - 1);
    if (sHash.get(S[left]) === 0) sHash.delete(S[left]);
    left++;
  }

  return answer;
};

const answer = solution("bacaAacba", "abc");

console.log(answer); // 3