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

5_hyun 2022. 8. 28. 03:24

모든 이나그램 찾기

해결법

이 문제는 해쉬, 투포인터를 활용해서 풀어야 하는 문제이다. 처음에 생각한 풀이와 답의 로직이 한 70% 정도는 유사했다.

하지만 해쉬의 자료구조인 Map를 비교할 때가 문제였다. 그래서 처음에는 배열로 바꿔서 비교했지만 쉽지 않았고 해결하지 못했다. 강사님의 코드를 보면 두 Map 중 하나를 for문으로 돌리고 나머지 Map를 맞춰보는 형식으로 풀었다. Map은 valuse 값이 0이 된다고 해서 삭제되는 것이 아니기에 만약 value가 0이면 delete로 삭제해줘야 한다.

코드

<html>
  <head>
    <meta charset="UTF-8" />
    <title>출력결과</title>
  </head>
  <body>
    <script>
      function compare(map1, map2) {
        if (map1.size !== map2.size) return false;
        for (let [key, val] of map1) {
          if (val !== map2.get(key) || !map2.has(key)) return false;
        }
        return true;
      }

      function solution(s, t) {
        let answer = 0;
        let n = t.length;

        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 sh = new Map();

        for (let i = 0; i < n - 1; 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 i = n - 1; i < s.length; i++) {
          if (sh.has(s[i])) sh.set(s[i], sh.get(s[i]) + 1);
          else sh.set(s[i], 1);

          if (compare(th, sh)) 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));
    </script>
  </body>
</html>

저작자표시 (새창열림)