반응형
Notice
Recent Posts
Recent Comments
Link
«   2025/01   »
일 월 화 수 목 금 토
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
Tags more
Archives
Today
Total
관리 메뉴

짧은코딩

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

코딩테스트 with JS/자바스크립트 알고리즘 문제풀이(인프런)

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

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>
반응형
저작자표시

'코딩테스트 with JS > 자바스크립트 알고리즘 문제풀이(인프런)' 카테고리의 다른 글

공주 구하기  (0) 2022.09.09
쇠막대기  (0) 2022.09.08
학급 회장(해쉬, Map)  (0) 2022.08.26
연속 부분수열 1(투포인터)  (0) 2022.08.24
공통원소 구하기(투 포인터)  (0) 2022.08.22
'코딩테스트 with JS/자바스크립트 알고리즘 문제풀이(인프런)' Related Articles more
Comments