5-8) 모든 아나그램 찾기(해시, 투포인터, 슬라이딩 윈도우)

김예지·2021년 9월 2일
1

문제

S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하 세요. 아나그램 판별시 대소문자가 구분됩니다. 부분문자열은 연속된 문자열이어야 합니다.
[입력설명]
첫 줄에 첫 번째 S문자열이 입력되고, 두 번째 줄에 T문자열이 입력됩니다.
S문자열의 길이는 10,000을 넘지 않으며, T문자열은 S문자열보다 길이가 작거나 같습니다.
[출력설명]
S단어에 T문자열과 아나그램이 되는 부분문자열의 개수를 출력합니다.

입력예제 1

bacaAacba abc

출력예제 1

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


문제 풀이

예습 이론

  • 해시: 아나그램
  • 투포인터: 부분 문자열
  • 슬라이딩 윈도우: 연속된 문자열

코드

  • 이 문제는 해시, 투포인터, 슬라이딩 윈도우를 사용한 문제다. 앞의 예제 7개를 총집합한 보스 문제라고 보면될듯!!!(해시: 아나그램 / 투포인터: 부분 문자열 / 슬라이딩 윈도우: 연속된 문자열)
  • 풀이 과정
    자바스크립트는 파이썬과 달리 해시맵을 비교하는 내장함수가 없다. 따라서, 해시맵을 비교하는 함수를 직접 작성해준다. (compareMaps 함수)

<html>
    <head>
        <meta charset="UTF-8">
        <title>출력결과</title>
    </head>
    <body>
        <script>
            //sH, tH를 비교하는 함수(파이썬에는 내장함수 있음, js에는 없어서 직접 만들어야해...)
            function compareMaps(map1, map2){
              if(map1.size!==map2.size) return false; //갯수 같은 것 먼저 비교
              for(let [key, val] of map1){
                if(!map2.has(key) || map2.get(key)!==val) return false; //map1의 key가 map2에 없을 때, false 리턴 || map2.get(key): map2의 value값, val: map1의 value값
              }
              return true;
              //console.log(map1.size);
            }
            function solution(s, t){
                let answer=0;
                let tH = new Map();
                let sH = new Map();
                //t의 해쉬맵 만들어줌 
                for(let x of t){
                  if(tH.has(x)) tH.set(x, tH.get(x)+1);
                  else tH.set(x, 1); 
                }
                let len=t.length-1;
                //len전까지 s의 해쉬맵 만들어줌
                for(let i=0; i<len; i++){
                  if(sH.has(s[i])) sH.set(s[i], sH.get(s[i])+1);
                  else sH.set(s[i], 1); 
                }
                let lt=0;
                //len부터 s의 해쉬맵 만듦
                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); //rt위치에있는 문자열 추가한 직후, 
                  if(compareMaps(sH, tH)) answer++; //(1)sH, tH가 같은지 비교하고, 같으면 answer++
                  sH.set(s[lt], sH.get(s[lt])-1); //(2)슬라이딩 윈도우! 현재 lt값 빼줌(-1)
                  if(sH.get(s[lt])===0) sH.delete(s[lt]); //(만약, 빼줄 값이 없다면(0이라 -1을 할 수 없으면) delete)
                  lt++;
                }
                return answer;
            }
            let a="bacaAacba";
            let b="abc";
            console.log(solution(a, b));
        </script>
    </body>
</html>
profile
내가 짱이다 😎 매일 조금씩 성장하기🌱

2개의 댓글

comment-user-thumbnail
2021년 9월 12일

9/12
1. 문자 + 문자는 되지만, 문자 - 문자는 안된다.
즉, 'ab'+'a'='aba'이지만, 'ab'-'a'=NaN이다.
2. map에서 for of 구문 쓸 때, for(let [key, val] of map)과 같이 사용할 것! 주의 또 주의!

답글 달기
comment-user-thumbnail
2021년 9월 13일

9/13
1. 해쉬맵끼리 같은지 비교하는 함수 작성(파이썬은 해쉬맵 비교 내장함수 있지만, 자바스크립트는 없기 때문에 직접 작성해줘야함)

function compareMaps(map1, map2){
              if(map1.size!==map2.size) return false; //갯수 같은 것 먼저 비교
              for(let [key, val] of map1){
                if(!map2.has(key) || map2.get(key)!==val) return false; //map1의 key가 map2에 없을 때, false 리턴 || map2.get(key): map2의 value값, val: map1의 value값
              }
              return true;
          
}
  1. lt 사용하기
  2. map에서 for of 구문 쓸 때, for(let [key, val] of map)과 같이 사용할 것! key:val 하나의 쌍이다. 주의 또 주의 또 주의 또 주의!!!
답글 달기