오늘은 3일에 거쳐 벽 느꼈던 알고리즘과 코드에 대해
하나하나 뜯어서 소개 / 정리 해보고자 한다.
이해하려다 외워버려서 다 외운 줄 알고 작성했다가
420 번째 도전만에 에러없이 원하는 값이 출력되었다.
우선 사용한 알고리즘은
투 포인트 알고리즘 , 해시 맵 , 슬라이딩 윈도우 정도 된다.
작성 순서와는 별개로 코드 보는 우선 순위를 앞에 적어두겠다.
문제
S문자열에서 T문자열과 아나그램이 되는
S의 부분문자열의 개수를 구하는 프로그램을 작성하세요.
아나그램 판별시 대소문자가 구분됩니다.
아나그램 뜻
7 .
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;
}
7-1.
각 인자의 사이즈를 비교해서 사이즈부터 다르다면 당연히 아나그램이 아닐 것이다.
7-2.
for of문을 돌려 key,val를 각각 구한 뒤 map2에 키가 있는지를 확인한다.
키가 있다면 앞의 if를 통과할 것이고, 그 뒤에 코드가 진행되는데
키를 가져와 map1의 value 랑 비교하게 된다.
(if문 앞에 달린 !를 유의하자)
저 조건이 다 통과되면 true이고 answer++하게 될 것이다.
1 .
function solution(s, t) {
let answer = 0;
let th = new Map();
let sh = new Map();
총 개수를 구하므로 answer = 0; 으로 시작
th, sh 각각 Map을 만들어준다.
2 .
for (let x of t) {
if (th.has(x)) th.set(x, th.get(x) + 1);
else th.set(x, 1);
}
th의 값과 sh의 값을 비교하면서 어떠한 작업을 수행하므로
어찌보면 기준이 될 th의 값을 만들어준다.
3 .
let len = t.length - 1;
4 .
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);
}
t.length = 3인데 -1해서 i < 2까지 포문을 돌리는 이유는
기본값 2개를 넣어두고 슬라이딩 윈도우로 하나추가 / 하나제거 / 비교
이런식의 구도를 가져가기 때문이다.
5 .
let lt = 0;
투 포인트 알고리즘을 사용하게 될 lt / rt 사용
6 .
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;
}
위에서 Len까지 돌린 값이 이미 있기때문에 rt는 len인 2부터 시작하게 된다.
if (compareMaps(sh, th)) answer++;
이 식에서 다른 함수가 등장하는데,
그 함수는 비교해서 아나그램이 아닌 상황을 다 제거하고 return true를 반환해주는 함수이다.
let a = "bacaAacba";
let b = "abc";
console.log(solution(a, b));
혹시 중간의 has, set , get , delete , size 메소드를 모른다면,
맵과 셋의 정리가 아주 잘된 문서 를 참고하기 바란다.
한 마디 : 반 정도 이해하고 쓰는것이기에 보고 이해 못하는게 당연하다.
이 글을 보고 이해한다면 당신은 알고리즘의 천재가 맞다.
그럼에도 헷갈리는 부분이 있으시다면 질문 남겨주시면
아는 한에서 성실하게 대답해드리겠습니다 !!
그리고 혹시 사실과 다른 점이 있다면 알려주시면 감사하겠습니다 !
