모든 아나그램 찾기

문제

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

 

문제풀이

---

• Map1 객체에 맨 처음 문자에서부터 연속부분 수열의 최대 문자열 길이까지의 문자에 대한 데이터(Key, Value)를 적재한다.
• 비교의 기준이 될 Map2 객체에 0~(T문자열 길이 - 1) 범위에 해당하는 문자를 적재한다.
• 해당 문제에서는 초기에 Map2 객체에 a와 b가 적재된다.
• 다음 인덱스 요소에서부터 반복문을 시작하여 Map1 객체에 포인터2가 현재 가리키고 있는 인덱스(시작 인덱스 요소)의 문자를 적재한다.
• 두 Map 객체를 비교한다.
• 비교가 끝난 뒤에 포인터1이 가리키고 있는 인덱스 요소를 Map1 객체에서 삭제한다.
• 삭제 시, value 값이 0일 경우에는 값이 존재하지 않기 때문에 delete 메서드를 통해 Key값을 완전히 삭제해주고 아닐 경우에는 1만큼 감산해준다.

코드

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 solution(s1, s2) {
  let answer = 0;
  let sH1 = new Map();
  let sH2 = new Map();
  let p1 = 0;
  let p2 = 0;

  for (let i = 0; i < s2.length; i++) {
    if (!sH1.has(s1[i]) || sH2.has(s2[i])) {
      sH1.set(s1[i], 1);
      sH2.set(s2[i], 1);
    } else {
      sH1.set(s1[i], sH1.get(s1[i]) + 1);
      sH2.set(s2[i], sH2.get(s2[i]) + 1);
    }
  }

  for(let i = 0; i < s1.length; i++) {
    if(!sH1.has(s1[++p2])) {
      sH1.set(s1[p2], 1);
    } else {
      sH1.set(s1[p2], sH1.get(s1[p2]) + 1);
    }
    if((p2 - p1) === 2) {
    	//두 포인터가 참조하고 있는 인덱스 간 차이가 2일 경우 => 연속부분수열의 원소 갯수 조건에 합당할 경우
      let result = compareMaps(sH1, sH2);
      if(result ===  true) answer++;
      sH1.delete(s1[p1++]);
    }
  }
  return answer;
}

let str1 = "bacaAacba";
let str2 = "abc";
console.log(solution(str1, str2));

---

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 solution(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));