효율성 - 8. 모든 아나그램 찾기(해쉬, 투포인터, 슬라이딩 윈도우)

문제

첫 문자열에서 두 번째 문자열과 아나그램이 되는 부분문자열의 개수  구하는 함수 작성하시오.
아나그램은 대소문자를 구분한다. 부분문자열은 연속된 문자열이어야 한다.

입력예제1
b a c a A a c b a
a b c

출력예제1 
3
출력설명: {b a c}, {a c b}, {c b a} 3개의 부분 문자열이 'abc'문자열과 아나그램이다.

 

 

풀이

입력 문자열

 

슬라이딩 윈도우를 만들고 아나그램인지 판별한다

 

슬라이딩 윈도우가 str1의 문자열길이 끝까지 갈때까지 아나그램을 판별한다.

 

코드

function 아나그램판별(obj1, obj2) {
  if(obj1.size !== obj2.size) return false;
  for (let [key, val] of obj1) {
    if(!obj2.has(key) || obj2.get(key) !== val) return false;
  }
  return true;
}

function solution(s, t){
  let answer=0;
  let len = t.length;
  let sH = new Map();
  let tH = new Map();

  for (let i = 0; i < len; i++) {
    if(tH.has(t[i])) tH.set(t[i], tH.get(t[i])+1);
    else tH.set(t[i], 1);
  }
  
  for (let i = 0; i < len; i++) {
    if (sH.has(s[i])) {
      sH.set(s[i], sH.get(s[i])+1);
    }
    sH.set(s[i], 1);
  }
  console.log(sH); //{'b' => 1, 'a' => 1, 'c' => 1}
  if(아나그램판별(sH, tH)) answer++;
  
  for (let i = len; i < s.length; i++) {
    //삭제
    if(sH.has(s[i-len])) {
      sH.set(s[i-len], sH.get(s[i-len])-1);
      if (sH.get(s[i-len]) == 0) sH.delete(s[i-len]);
    }
    //추가
    if (sH.has(s[i])) sH.set(s[i], sH.get(s[i])+1);
    else sH.set(s[i], 1);
    console.log(sH);
    //{'a' => 2, 'c' => 1}
    //{'a' => 1, 'c' => 1, 'A' => 1}
    //{'a' => 2, 'A' => 1}
    //{'a' => 1, 'A' => 1, 'c' => 1}
    //{'a' => 1, 'c' => 1, 'b' => 1}
    //{'c' => 1, 'b' => 1, 'a' => 1}
    if (아나그램판별(sH, tH)) answer++;
  }
  
  return answer;
}
let a="bacaAacba";
let b="abc";
console.log(solution(a, b));

 

 

출처

자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의