25.모든 아나그램 찾기 - Hash, twoPointer, slidingWindow

Updated:


모든 아나그램 찾기(hash, twoPointer, slidingWindow)

🔍 문제

S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하세요.

아나그램 판별시 대소문자가 구분됩니다. 부분문자열은 연속된 문자열이어야 합니다

🔹 입력설명

첫 줄에 첫 번째 S문자열이 입력되고, 두 번째 줄에 T문자열이 입력됩니다.

S문자열의 길이는 10,000을 넘지 않으며, T문자열은 S문자열보다 길이가 작거나 같습니다

🔹 출력 설명

S단어에 T문자열과 아나그램이 되는 부분문자열의 개수를 출력합니다

🔹 입력예제 1

bacaAacba

abc

🔹 출력 예제 1

3

출력설명: {bac}, {acb}, {cba} 3개의 부분문자열이 “abc”문자열과 아나그램입니다


📌 풀이

11

22

<head>
  <meta charset="UTF-8">
  <title>출력결과</title>
</head>

<body>
  <script>
    function compareMaps(map1, map2) { // 먼저 sH 와 tH의 사이즈를 비교
      if (map1.size !== map2.size) return false; // 만약 sH 와 tH 의 사이즈가 다를 경우에 는 바로 false return
      // 사이즈가 이제 같으면 sH 와 tH 값이 같은지 비교 시작
      for (let [key, val] of map1) {
        // map 2 에 key 값이 있는지 보는거, tH 에 sH의 key 값이 없으면 false return 또는 key 는 있는 데 value 값이 서로 다르면 또 false 해줘야 함 tH 의 value 값과 sH 의 value 값이 서로 같지 않을 때, return false;
        if (!map2.has(key) || map2.get(key) !== val) return false;  
      }
      return true; // 위의 조건들을 다 통과하면 true return 
    }

    function solution(s, t) {
      let answer = 0;
      let tH = new Map();
      let sH = new Map();
      for(let x of t) { // tH hash Map Counting
        if(tH.has(x)) tH.set(x, tH.get(x) + 1);
        else tH.set(x, 1);
      }
      let len = t.length - 1 // 하나 적게 해서 sH 의 sliding window 가 투포인터 설정 전에 하나 빼고 먼저 탐색 할수 있게 범위 설정
      for (let i=0; i<len; i++) { // i 로 for 문 도는 거니까 s[i] 헷갈리지 않게 잘 넣기
        if(sH.has(s[i])) sH.set(s[i], sH.get(s[i]) + 1);
        else sH.set(s[i], 1);
      }
      // sliding window 그리고 two pointer 로 돌기
      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++; // 추가 하면 바로 비교 하기 두개를 비교했는데 같으면 answer cnt ++
        sH.set(s[lt], sH.get(s[lt]) - 1) // 비교 했으니까 lt 부분을 빼줘야 함
        if(sH.get(s[lt]) === 0) sH.delete(s[lt]); // 빼줬는데 만약 lt의 value 값이 0 이면 delete 해줘야 함
        lt++; // lt  증가 해주고 다시 for loop 시작 
      }
      return answer;
    }
    let a = "bacaAacba";
    let b = "abc";
    console.log(solution(a, b));
  </script>
</body>

Leave a comment