모든 아나그램 찾기
(해쉬, 투포인터, 슬라이딩 윈도우)
S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하세요. 아나그램 판별시 대소문자가 구분됩니다. 부분문자열은 연속된 문자열이어야 합니다.
나의 풀이
function compareMaps(map1, map2) {
if (map1.size !== map2.size) return false;
for (let [key, val] of map1) {
let tmp = map2.get(key);
if (tmp !== val || (tmp === undefined && !map2.has(key))) return false;
}
return true;
}
function solution(s, t) {
let answer = 0;
let sH = new Map();
let tH = new Map();
let i = 0;
while (i < t.length) {
if (tH.has(t[i])) tH.set(t[i], tH.get(t[i]) + 1);
else tH.set(t[i], 1);
if (sH.has(s[i])) sH.set(s[i], sH.get(s[i]) + 1);
else sH.set(s[i], 1);
i++;
}
if (compareMaps(sH, tH)) answer++;
for (let idx = 0; idx < s.length; idx++) {
let lt = s[idx];
let rt = s[idx + t.length];
if (sH.get(lt) === 1) sH.delete(lt);
else sH.set(lt, sH.get(lt) - 1);
if (sH.has(rt)) sH.set(rt, sH.get(rt) + 1);
else sH.set(rt, 1);
if (compareMaps(sH, tH)) answer++;
}
return answer;
}
let a = 'bacaAacba';
let b = 'abc';
console.log(solution(a, b));정답 풀이
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));배운 점
정답 풀이와 나의 풀이는 비슷한 양상으로 진행된다. 신경써서 구현 했던 부분은 Map()간의 비교를 하는 함수 compareMaps() 함수이다. 가장 먼저 Map.size를 활용하여 각 Map의 크기, 다시 말해 key의 갯수가 일치하는지 여부를 확인했다.
key의 갯수의 비교를Map.size를 통해 진행하기 위해 각각의key의value가 0인 경우,Map.delete(key)를 통해서 삭제해주는 과정을 진행했다.
이후에는 각각의 key,value를 for문을 통해 검증하며 해당 key가 비교 대상인 Map에 존재하는지, 존재한다면 해당 key의 value가 동일한지 여부를 확인하여 true 혹은 false를 return 하도록 했다.
개선할 점
앞서 언급한 바와 같이 풀이 과정에서의 연산 횟수는 정답 풀이와 나의 풀이가 동일하지만, 코드의 효율성과 가독성 면에서는 차이가 있다. 나의 풀이는 첫번째 window의 크기를 검증해야하는 아나그램의 크기와 동일하게 생성한 이후에 반복문을 통해 슬라이딩을 진행했다. 그렇기 때문에 슬라이딩을 진행하기 전에 첫번째 window가 아나그램인지 여부를 확인하기 위해 compareMaps() 함수를 사용해야했다. 하지만 정답 풀이에서는 아나그램의 길이보다 하나 짧은 문자열을 Map에 지정하고, 반복문 속에서 rt를 추가한 후에 compareMaps()로 비교하고, lt를 제거하여 다시 아나그램의 길이보다 하나 짧은 문자열을 다시 만든 상태로 반복을 진행했다. 아래의 그림은 이해를 돕기 위한 비교 표이다.
