[JavaScript/section 5] 08 - 모든 아나그램 찾기

📌 08 - 모든 아나그램 찾기(해쉬, 투포인터, 슬라이딩 윈도우)

S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 문자이다.

나의 풀이 방법

아나그램이 되는지 확인하기 위해 해쉬의 특징을 사용했고, 부분 문자열을 구하기 위해 슬라이딩 윈도우 방식과 slice() 함수를 사용하였다. 문제를 해결하고 나서 잘 풀었다고 생각했지만.. 코드를 다시 보니 부분 문자열을 구하는 부분에 있어서 이중 for 문을 사용했기 때문에 효율성(시간 복잡도) 측면에서는 좋지 않다라고 생각했다.

• for 문을 돌기 전에 t의 해쉬 값을 구한다.
• for 문을 돌면서 s문자열에 slice() 함수를 이용하여 i 번째 인덱스부터 t문자열 길이 + i 전까지를 잘라준 후 str 변수에 저장한다. (부분 문자열을 구하는 과정)
•  str의 해쉬 값을 구한다.
• compareMaps 함수를 이용해 t문자열과 s의 부분문자열이 anagram이 맞는지 검사한다.
• sH를 clear() 함수를 이용해 초기화 해준다. 

👍 강사님 풀이 방법

부분 문자열 구하는 방식에서 슬라이딩 윈도우와 투 포인터 알고리즘을 이용하여 문제를 풀이 해주셨다.😀

시간 복잡도가 O(N)이기 때문에 slice() 함수를 이용했을 때보다 효율성 측면에서 더 좋은 풀이 방법이라고 생각한다.

• 초기에 윈도우를 세팅하기 위해서 0부터 t문자열 길이 - 1까지 s의 부분문자열의 해쉬 값을 구한다.
• 포인터 rt는 t문자열의 길이 -1부터 시작하여 끝까지 for 문을 돌면 된다. t문자열의 길이 -1부터 시작하는 이유는 위에서 윈도우를 미리 세팅해놨기 때문이다.
• 포인터 rt가 한 칸씩 이동하면서 현재 해쉬 값을 구한다. 
• compareMaps 함수를 이용해 t문자열과 s의 부분문자열이 anagram이 맞는지 검사한다.
• 검사가 끝나면 포인터 lt에 해당하는 값의 value를 -1 해준다. 이 때 value가 0이라면 delete()함수를 이용해 Map 객체에서 삭제한다.
• 포인터 lt를 1 증가시킨다.

 

📝 풀이

// 나의 풀이 방법
function 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;
  }
  return true;
}

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

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

  let str = '';
  let tlen = t.length;
  let slen = s.length;

  for (let i = 0; i < slen - 2; i++) {
    sH.clear();
    str = s.slice(i, i + tlen);

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

    if (compareMaps(sH, tH)) answer++;
  }

  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, value] of map1) {
    if (!map2.has(key) || map2.get(key) !== value) return false;
  }
  return true;
}

function solution(s, t) {
  let answer = 0;
  let sH = new Map();
  let tH = 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));