[인프런] Node.js / 섹션5-효율성(해시&슬라이싱 윈도우&투포인터 알고리즘) / 8. 모든 아나그램 찾기

S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하세요.

아나그램 판별시 대소문자가 구분됩니다. 부분문자열은 연속된 문자열이어야 합니다.

첫 줄에 첫 번째 S문자열이 입력되고, 두 번째 줄에 T문자열이 입력됩니다.

S문자열의 길이는 10,000을 넘지 않으며, T문자열은 S문자열보다 길이가 작거나 같습니다.

 

풀이

let answer = 0;

function isAnagram(arr, t) {
  let sHCopy = new Map(arr); // 원본 수정하면 안되므로 복사본 만듦
  for (let j = 0; j < t.length; j++) {
    if (!sHCopy.has(t[j]) || sHCopy.get(t[j]) == 0) break;
    sHCopy.set(t[j], sHCopy.get(t[j]) - 1);
    if (j === t.length - 1) {
      answer++;
    }
  }
}

function solution(s, t) {
  let sH = new Map();
  for (let i = 0; i < t.length; i++) {
    if (sH.has(s[i])) sH.set(s[i], sH.get(s[i]) + 1);
    else sH.set(s[i], 1);
  }
  isAnagram(sH, t);

  for (let i = t.length; i < s.length; i++) {
    sH.set(s[i - t.length], sH.get(s[i - t.length]) - 1);
    if (sH.has(s[i])) sH.set(s[i], sH.get(s[i]) + 1);
    else sH.set(s[i], 1);
    isAnagram(sH, t);
  }
  return answer;
}

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

푸는데 되게 오래 걸렸다. 많은 연습이 필요할 것 같다.

 

강사 풀이

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(s, t) {
  let answer = 0;
  let tH = new Map();
  let sH = new Map();
  for (let x of t) {
    if (tH.has(x)) tH.set(x, tH.get(x) + 1);
    else tH.set(x, 1);
  }
  let len = t.length - 1;
  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);
  }
  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);
    if (compareMaps(sH, tH)) answer++;
    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));