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

문제 

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

 

내 풀이

투포인터를 활용한 슬라이딩 윈도우를 만들어서 아나그램인지 판단하기로 했다.

문자열이 주어지다보니 전에 풀었던 아나그램 예제처럼 베이직한 슬라이딩 윈도우를 사용하기에는 무리가 있었기 때문에 투포인터를 사용해서 슬라이딩 윈도우를 구현해보았다.

function isAnagram(str1, str2) {
  let answer = true;
  let sH = new Map();
  for (let x of str1) {
    if (sH.has(x)) sH.set(x, sH.get(x) + 1);
    else sH.set(x, 1);
  }
  for (let x of str2) {
    if (!sH.has(x) || sH.get(x) == 0) return false;
    sH.set(x, sH.get(x) - 1);
  }
  return answer;
}

function solution(s, t) {
  let result = 0;
  let lt = 0;
  for (let rt = t.length - 1; rt < s.length; rt++) {
    const tmp = s.slice(lt, rt + 1);
    if (isAnagram(tmp, t)) {
      result++;
    }
    lt++;
  }
  return result;
}

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

 

이 풀이에서 몇 가지 단점을 찾아볼 수 있었다.

먼저 순회할 때마다 slice 메서드를 사용해 부분배열을 복사하기 때문에 O(N) 시간복잡도를 가질 수 없다.

그리고 isAnagram 함수가 매번 호출될 때마다 해쉬맵을 생성한다.

 

나는 O(N)의 시간복잡도로 코드를 수정하고 싶고, 매번 해쉬맵을 생성하지 않고 싶다.

 

강의 풀이

 

아나그램인지 아닌지 판단하는 것은 부분문자열에 특정 단어가 포함된 갯수의 일치여부를 확인하는 것이다.

먼저 t에 대한 해쉬맵을 생성한다.

예제에서는 t가 abc로 주어졌기 때문에 해쉬맵을 생성하면 { a=>1, b=>1, c=>1 } 이런 형식을 가지게 될 것이다.

 

그리고 s에 대한 해쉬맵을 생성한다.

일단 rt가 가리키는 이전의 요소들만 해쉬맵에 저장한다.

예제를 기준으로 b,a만 해쉬맵에 저장하고 rt는 그 다음 요소인 c를 가리키게 한다.

 

그리고 rt가 가리키는 요소를 해쉬맵에 추가하고 t의 해쉬맵과 s의 해쉬맵을 비교한다.

비교할 때는 다음의 조건을 확인한다.

1. 두 개의 해쉬맵 사이즈가 같아야한다.

2. 각 해쉬맵의 key에 대한 value값이 같아야한다.

만일 위의 두 조건을 만족하지 않으면 부분문자열은 아나그램이 아닌 것이다.

 

해쉬맵끼리 비교를 했으면 슬라이딩 윈도우를 옆으로 밀어야한다.

그러기 위해서 lt가 가리키는 요소의 값을 s의 해쉬맵에서 하나 뺀다.

예제에서는 lt는 b를 가리키고 있으므로 s의 해쉬맵에서 key가 b에 해당하는 value를 하나 빼준다.

그렇게 되면 s의 해쉬맵은 다음과 같다.

{ b=>1, a=>1, c=>1 } ➡ { b=>0, a=>1, c=>1 }

key가 b일 때 value는 0이 된다. value가 0이라는 것은 더이상 부분문자열에 포함되지 않는다는 의미이므로 해쉬맵에서 제거해야한다. 그 다음에 lt를 한 칸 옆으로 옮겨준다.

 

이 과정을 추상화 시켜보면 다음과 같다.

1. rt가 가리키는 값을 s의 해쉬맵에 추가한다.

2. t의 해쉬맵과 s의 해쉬맵을 비교한다.

3. lt가 가리키는 값을 s의 해쉬맵에서 하나 삭제한다.

4. lt를 오른쪽으로 옮긴다.

function compareHash(map1, map2) {
  if (map1.size !== map2.size) return false;
  for (const [key, value] of map2) {
    if (!map1.has(key)) return false;
    if (map1.get(key) !== value) return false;
  }
  return true;
}

function solution(s, t) {
  const sH = new Map();
  const tH = new Map();
  let lt = 0;
  let result = 0;
  for (const x of t) {
    if (tH.has(x)) tH.set(x, tH.get(x) + 1);
    else tH.set(x, 1);
  }
  for (let i = 0; i < t.length - 1; i++) {
    if (sH.has(s[i])) sH.set(s[i], sH.get(s[i]) + 1);
    else sH.set(s[i], 1);
  }
  for (let rt = t.length - 1; 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 (compareHash(sH, tH)) result++;
    sH.set(s[lt], sH.get(s[lt]) - 1);
    if (sH.get(s[lt]) === 0) sH.delete(s[lt]);
    lt++;
  }
  return result;
}

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

 

이렇게 되면 매번 해쉬맵을 생성하지 않아도 된다.

하지만 rt가 s를 순회할 때마다 해쉬맵끼리 일치여부를 비교하는 함수를 수행하므로 O(N)을 만족하지 않는다.

 

O(N)을 만족하기 위해선 두개의 해쉬맵을 비교하는 것이 아니라 하나의 해쉬맵을 활용하면 된다.

해당 코드가 있지만 아직 완벽하게 이해가 되지 않는다. 복습할 때 다시 한 번 정리해야겠다.