2022/01/31) 8. 모든 아나그램 찾기(해쉬, 투포인터, 슬라이딩 윈도우) [효율성(투포인터 알고리즘, 슬라이딩윈도우, 해쉬)]

1. 문제

<모든 아나그램>
: S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성한다. 아나그램 판별시 대소문자가 구분된다. 부분문자열은 연속된 문자열이어야 한다.

2. 해결 방법

1. 먼저 t문자열을 hash한다.
2. 맨 마지막꺼(rt)를 제외한 것들을 세팅한다.
3. for문안에서 해야 할 것들이다.
   맨 마지막꺼를 세팅(has/set/get 이용)하는데, 그러면 창문하나가 완성이 된다. 그 후 비교(compareMaps)를 한다. 그리고 이제 투포인터로 창문을 이동시켜야 하므로, lt를 뺀다.(주의할 점 : 새로운 lt값은 원래 있던 값이 되므로, Map메소드를 이용해서 추가할 필요가 없다. 그냥 lt값을 증가시켜주기만 하면 된다. 추가로 lt값이 0이라면 그 key자체를 삭제해 주어야 한다.
4. 정리하면, 추가(rt)하고 비교(copareMaps)하고 빼기(sH.set(s[lt], sH.get(s[lt])-1); !
   추가하고 비교하고 빼기!!!

3. 정답

        <script>
            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;
                }
                return true;
            }
            function solution(s, t){
                let answer=0;
                let tH = new Map();
                let sH = new Map();
                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;
                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;
                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++;
                    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>

4. 내 코드와 비교 그리고 반성

한 번 공부를 했지만 그래도 막막할 땐 그냥 코드 따라치기를 반복해보자.

        <script> //저녁에 다시 한 번 더 복습한다.
            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;
                }
                return true;
            }
            function solution(s, t){
                let answer = 0;
                let tH = new Map();
                let sH = new Map();
                for(let x of t){
                    //t의 해쉬 완성
                    if(tH.has(x)) tH.set(x, tH.get(x)+1);
                    else tH.set(x, 1);
                }
                let len = t.length - 1; //2[0,1,2]
                for(let i = 0; i < len; i ++){ //창문 총 3칸중, 2칸 완성[0,1]
                    if(!sH.has(s[i])) sH.set(s[i],1);
                    else sH.set(s[i], sH.get(s[i]) + 1);
                }
                let lt = 0;
                for(let rt = len; rt < s.length; rt ++){ 
                    //창문 총 3칸중, 1칸 완성[2]
                    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++;
                    //빼기
                    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>