모든 아나그램 찾기 (해시, 슬라이싱 윈도우)

문제

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

제한 사항

입출력 예

풀이

// 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;
}

// 메인 솔루션
function solution2(str, target) {
  let answer = 0;
  let sH = new Map(); // str용
  let tH = new Map(); // target용

  // target 문자열의 map을 만드는 과정
  for (let x of target) {
    if (tH.has(x)) {
      tH.set(x, tH.get(x) + 1);
    } else {
      tH.set(x, 1);
    }
  }

  // target의 길이 -1 만큼 sh를 셋팅
  let k = target.length - 1;
  for (let i = 0; i < k; i++) {
    if (sH.has(str[i])) {
      sH.set(str[i], sH.get(str[i]) + 1);
    } else {
      sH.set(str[i], 1);
    }
  }

  // 윈도우 슬라이싱 기법
  for (let i = k; i < str.length; i++) {
    // 문자 하나를 map에 추가한다.
    if (sH.has(str[i])) {
      sH.set(str[i], sH.get(str[i]) + 1);
    } else {
      sH.set(str[i], 1);
    }
    // 추가한 직후 targetMap과 비교한다.
    if (compareMaps(sH, tH)) answer++;

    // map 앞에 것을 뺴준다.
    sH.set(str[i - k], sH.get(str[i - k]) - 1);

    // 뺸 후 값이 0이면 해당 키는 제거해준다.
    if (!sH.get(str[i - k])) {
      sH.delete(str[i - k]);
    }
  }
  return answer;
}
a = "bacaAacba";
b = "abc";
console.log(solution2(a, b));

• 해쉬(맵 자료구조), 투포인터, 슬라이딩 윈도우를 모두 사용하는 알고리즘이다.
• 슬라이딩 윈도우 기법이 투포인터의 활용으로 생각하면 된다.
• 주석에 전반적인 설명을 해두어서 잘 읽어보고 이해를 확실히 하도록 하자.