[투포인터/해시/슬라이딩윈도우] 모든 아나그램 찾기

자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다.

 

 

 

 

📋 문제

아나그램이란 두 문자열이 알파벳의 나열 순서는 다르지만 그 구성이 일치한 두 문자열을 말한다.

 

긴 문자열 A와 짧은 문자열 B가 주어진다.

A 문자열에서 B 문자열과 아나그램이 되는 A의 부분 문자열 개수를 구해 출력한다.

 

아나그램 판별 시 대소문자가 구분되며 부분 문자열은 연속된 문자열이다.

 

 

👉 입력

첫 번째 줄에 A 문자열이 입력된다.

두 번째 줄에 B 문자열이 입력된다.

이때 A 문자열의 길이는 10,000을 넘지 않으며 B 문자열은 A 문자열보다 길이가 작거나 같다.

 

 

👈 출력

A의 연속 부분 문자열이 B 문자열과 아나그램이 되는 개수를 출력한다.

 

 

📝 풀이

 

function compare(map, t) {
  for (const x of t) {
    if (!map.has(x) || map.get(x) === 0) return false;
    map.set(x, map.get(x) - 1);
  }

  return true;
}
function solution(s, t) {
  let answer = 0;

  for (let i = 0; i < s.length - t.length + 1; i++) {
    let str = s.substring(i, i + t.length);
    let map = new Map();
    for (const x of str) {
      if (map.has(x)) map.set(x, map.get(x) + 1);
      else map.set(x, 1);
    }
    if (compare(map, t)) answer++;
  }

  return answer;
}

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

 

solution 함수에서 for문을 돌며 s의 연속 부분 문자열을 만든다.

Map 객체에 이 부분 문자열의 각 문자를 순회하며 문자와 해당 문자의 등장 횟수를 정리한다.

 

compare 함수에서는 각 부분 문자열의 문자 현황과 비교할 문자열 t를 인자로 받는다.

그리고 t의 각 문자를 순회하며 Map과 비교해 이 두 문자열이 아나그램인지 판별한다.

 

다시 solution으로 돌아와 이 두 문자열이 아나그램이라면 answer에 1을 더하고 아니면 넘어간다.

 

해쉬, 투 포인터, 슬라이딩 윈도우를 다 써서 풀이를 구현하는 것이 목적이었는데 해쉬에 슬라이딩 윈도우가 쪼끔 가미된 풀이가 나왔다.

 

 

function compareMaps(map1, map2) {
    if (map1.size !== map2.size) return false;

    for (const [k, v] of map1) {
        if (!map2.has(k) || map2.get(k) !== v) return false;
    }

    return true;
}

function solution(s, t) {
    let answer = 0;
    let mapS = new Map();
    let mapT = new Map();

    for (const i of t) {
        if (mapT.has(i)) mapT.set(i, mapT.get(i) + 1);
        else mapT.set(i, 1);
    }

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

    let start = 0;
    for (let end = len; end < s.length; end++) {
        if (mapS.has(s[end])) mapS.set(s[end], mapS.get(s[end]) + 1);
        else mapS.set(s[end], 1);

        if (compareMaps(mapS, mapT)) answer++;
        mapS.set(s[start], mapS.get(s[start]) - 1);
        if (mapS.get(s[start]) === 0) mapS.delete(s[start]);
        start++;
    }

    return answer;
}

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

 

이 풀이는 해쉬, 투 포인터, 슬라이딩 윈도우가 모두 들어있다.

먼저 이 풀이에서는 문자열 t의 문자 현황을 파악하고 시작한다.

그리고 문자열 s의 첫 부분 문자열이 될 부분 문자열의 문자 현황을 파악한다.

 

그리고 투 포인터를 돌려 부분 문자열을 하나씩 만들어 나가고 그와 함께 compareMaps 함수에서 문자 현황을 비교해 두 문자열이 아나그램인지 판별한다.

 

 

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

    for (const i of t) {
        map.set(i, (map.get(i) || 0) - 1);
    }

    for (let i = 0; i < t.length - 1; i++) {
        map.set(s[i], (map.get(s[i]) || 0) + 1);
        if (map.get(s[i]) === 0) map.delete(s[i]);
    }

    let start = 0;
    for (let end = t.length - 1; end < s.length; end++) {
        map.set(s[end], (map.get(s[end]) || 0) + 1);

        if (map.get(s[end]) === 0) map.delete(s[end]);
        if (map.size === 0) answer++;

        map.set(s[start], (map.get(s[start]) || 0) - 1);
        if (map.get(s[start]) === 0) map.delete(s[start]);
        start++;
    }
    return answer;
}

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

 

이 코드는 바로 위의 코드를 다른 함수 없이 solution 함수 하나만으로 같은 효과를 내도록 한 것이다.

여러 가지 아이디어를 하나로 섞는 건 많이 보고 배워야 할 것 같다.