JS알고리즘 | 아나그램이 되는 부분문자열의 개수 구하기

해시, 투포인터, 슬라이딩 윈도우 알고리즘을 이용해서 풀어보는 문제

 

1. 문제

주어지는 문자열에서 아나그램이 되는 부분 문자열의 개수 구하기.

부분문자열은 연속된 문자열이다. 

입력예제 | 문자열 bacaAacba, 부분 문자열 abc

출력예제 | 3 

 

 

2. 접근방법

주어진 부분문자열과 문자열의 일부(부분문자열의 length-1)를 객체로 바꾼다.

포인터 지점을 찍어놓고 for문으로 한칸씩 이동하면서 부분문자열의 length만큼의 자리를 비교한다.

아나그램이 아닐 경우 포인터를 다음 인덱스로 이동시키고,

아나그램일 경우 answer를 카운팅하고 다음인덱스로 이동시킨다. 

 

 

3. 풀이방법

1) answer에 개수를 카운팅 해주기위해서 0으로 세팅한다. 

let answer = 0;

 

2) 찾아야하는 아나그램이 되는 연속된 부분문자열이기 때문에 주어진 부분문자열의 알파벳과 값을 객체형태로 가지고 있어야한다. map 객체를 사용한다. 

let map1 = new Map();
let map2 = new Map();

for (let x of t) {
	if (map2.has(x)) {
    	map2.set(x, map2.get(x) + 1);
    } else {
    	map2.set(x, 1);
    }
}

 

3) 부분문자열의 크기만큼 슬라이딩 윈도우 기본 세팅을 해준다. 

let len = t.length -1;

 

주어진 문자열 중에서 가장 앞에 2개의 문자만 객체로 세팅한다.

length를 부문분자열의 크기만큼 하지않고 -1을 해주는 이유는

부분문자열의 크기가 3일때, 2는 고정으로 계속 두고 한자리만 바꾸면서 비교를 진행해야하기 때문이다. 

for (let i = 0; i < len; i++) {
	if (map1.has(s[i])) {
    	map1.set(s[i], map1.get(s[i] + 1);
    } else {
    	map1.set(s[i], 1);
    }
}

 

4) for문으로 슬라이딩 윈도우로 한칸씩 이동하면서

1개 추가해서 3개씩 비교하고(부분문자열의 length) 아나그램이 아닐 경우 빼주고 반복한다. 

비교 이후에 빼주는 작업을 하기위해서 투 포인터 변수 작성해준다.

let lt = 0;
rt는 for 반복문 안에 선언

for (let rt = len; rt < s.length; rt++) {
    if (map1.has(s[rt])) {
      map1.set(s[rt], map1.get(s[rt]) + 1);
    } else {
      map1.set(s[rt], 1);
    }

	// 비교
    if (compareMaps(map1, map2)) {
      answer++;
    }
    
    // 비교 이후에 왼쪽 포인터 빼주는 작업 
    map1.set(s[lt], map1.get(s[lt]) - 1); // 기존 값보다 1작게 가져와서 다시 세팅
    if (map1.get(s[lt]) === 0) {
      map1.delete(s[lt]);
    }
    lt++;
}

 

5) 비교하는 함수 작성

부분문자열의 개수가 같은지 확인

key값이 같은지, value 값이 같은지 확인

const compareMaps = (map1, map2) => {
	if (map1.size !== map2.size) {
    	return false;
    }
    for (let [key, value] of map1) {
    	if (!map2.has(key) || map2.get(key) !== value) {
        	return false;
        }
    }
    retrun true; // 모두 아니면 같은 것으므로 true 반환
}

 

 

4. 코드

const solution = (s, t) => {
  // 아나그램이 되는 연속된 부분문자열 개수
  let answer = 0;

  let map1 = new Map(); // 문자열을 map 객체로
  let map2 = new Map(); // 부분문자열을 map 객체로

  // 찾아야하는 연속된 부분문자열을 map객체로 만듬
  for (let x of t) {
    if (map2.has(x)) {
      map2.set(x, map2.get(x) + 1);
    } else {
      map2.set(x, 1);
    }
  }

  // 슬라이딩 윈도우 할 때 길이가 3이면 2개를 먼저 세팅해 놓는 것
  let len = t.length - 1;

  for (let i = 0; i < len; i++) {
    if (map1.has(s[i])) {
      map1.set(s[i], map1.get(s[i]) + 1);
    } else {
      map1.set(s[i], 1);
    }
  }

  let lt = 0;

  // 슬라이딩 윈도우이기 때문에 rt는 len길이를 시작점으로 세팅
  // 추가해서 3개로 맞춰주고
  for (let rt = len; rt < s.length; rt++) {
    if (map1.has(s[rt])) {
      map1.set(s[rt], map1.get(s[rt]) + 1);
    } else {
      map1.set(s[rt], 1);
    }

    // 3개이니까 이제 비교가능
    if (compareMaps(map1, map2)) {
      answer++;
    }

    // 비교 이후에 왼쪽 포인터 빼주는 작업 
    map1.set(s[lt], map1.get(s[lt]) - 1); // 기존 값보다 1작게 가져와서 다시 세팅
    if (map1.get(s[lt]) === 0) {
      map1.delete(s[lt]);
    }
    lt++;
  }
  return answer;
}

const compareMaps = (map1, map2) => {
  if (map1.size !== map2.size) { // 1. 개수가 같은지 확인
    return false;
  }
  for (let [key, value] of map1) { // 2. key 값이 같은지 확인
    if (!map2.has(key) || map2.get(key) !== value) { // 3. value 값이 같은지 확인
      return false;
    }
  }
  return true;
}

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