[인프런 섹션5] 모든 아나그램 찾기 (Javascript)

👩🏻‍💻문제링크

[인프런 섹션5] 모든 아나그램 찾기 (Javascript)
유료 강의인 관계로 문제 설명은 생략합니다.

✍️Idea Sketch

2021-06-25

1. 부분문자열을 일일이 str.substring()으로 잘라내야하나? 다른 방법은 없나?

2. 문자열 T를 hash로 전환

3. 2번과 동시에 문자열 S를 문자열 T의 길이만큼만 hash로 전환

for (let i=0; i<len; i++) {
        hashS.set(strS[i], (hashS.get(strS[i]) || 0) + 1);
        hashT.set(strT[i], (hashT.get(strT[i]) || 0) + 1);
    }

주의
초기값 hashS가 hashT와 일치하는지 확인해야 함

3. 그 다음 부분문자열 구하기 (hashS 업데이트)

• 방법 1. left, right 변수를 사용해 hash.set(val, -1), hash.set(val, +1)
• 방법 2. 변수 i 하나만 사용하여 i번째 문자, i-len 연산

hashS.set(strS[i], (hashS.get(strS[i]) || 0) + 1);
hashS.set(strS[i-len], hashS.get(strS[i]) - 1);

5. hashS와 hashT의 일치여부 확인

• true/false에 따라 cnt++를 하기 위해, isEquel() 함수 정의

function isEquel(hashS, hashT) {
    for (let [key, val] of hashT) {
        if (val !== hashS.get(key)) return false;
    }
    return true;
}
 
if (isEquel(hashS, hashT)) cnt++;

✍️소스코드

2021-06-25

function isEquel(hashS, hashT) {
    for (let [key, val] of hashT) {
        if (val !== hashS.get(key)) return false;
    }
    return true;
}
 
function solution(strS, strT) {
    let cnt = 0;
    let hashS = new Map(), hashT = new Map();
 
    let len = strT.length;
    for (let i=0; i<len; i++) {
        hashS.set(strS[i], (hashS.get(strS[i]) || 0) + 1);
        hashT.set(strT[i], (hashT.get(strT[i]) || 0) + 1);
    }
 
    if (isEquel(hashS, hashT)) cnt++;
 
    for (let i=len; i<strS.length; i++) {
        hashS.set(strS[i], (hashS.get(strS[i]) || 0) + 1);
        hashS.set(strS[i-len], hashS.get(strS[i-len]) - 1);
        if(isEquel(hashS, hashT)) cnt++;
    }
 
    return cnt;
}