반응형
📌강의 정리
해쉬, 슬라이딩윈도우, 투포인터 알고리즘의 종합선물세트같은 문제이다.
슬라이딩 윈도우를 b의 길이만큼 만들지만 투포인터 알고리즘을 써서 계속 a와b를 비교하며
a의 슬라이딩윈도우를 한칸씩 옆으로 옮긴다.
슬라이딩 윈도우를 만들때는 b의 길이 -1 을 해서 만들고 옮기면서 하나씩 더하고 빼주며 옮긴다.
비교할때는 해쉬를 사용하여 키,밸류 형태로 비교한다.
키, 밸류 형태로 비교할때는 size가 맞는지와 키는 있는지, 키 당 밸류의 개수가 맞는지를 비교한다.
📌느낀점
문제를 볼때 강의시간이 27분이라 정말 엄청 어려운 문제인줄 알았는데 생각보다는 할만했다.
물론 생각보다 할만했다는 거지 결코 쉽지는 않았다.
이 문제의 까다로운 점이 있다면 지금까지의 알고리즘들을 다 써야 할줄은 물론이고 그것들을 연결시켜야 한다는 점일것이다.
나는 처음의 알고리즘의 흐름은 강사님과 같았지만 구현하는 부분에서 살짝 달랐으며
map2개를 비교하는 함수도 나의 것은 재사용성이나 확장성이 거의 없는 반면에 강사님은 정의가 정확하며 재사용성 또한 뛰어나다.
함수를 새로 만들때 항상 그 함수가 원래 기능해야하는 바를 정확하게 그 의미에 맞춰 만드는 노력을 해야한다.
//나의 코드
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
function compareMaps(map1, map2) {
let cnt = 0;
for (let [k, v] of map2) {
if (map1.get(k) === v) cnt++;
}
return cnt;
}
function solution(a, b) {
let answer = 0;
let lt = 0;
let rt = lt + b.length;
let tmp = 0;
let map2 = new Map();
for (let j = 0; j < b.length; j++) {
if (map2.has(b[j])) map2.set(b[j], map2.get(b[j]) + 1);
else map2.set(b[j], 1);
}
console.log("map2 = ", map2);
for (let i = 0; i < a.length; i++) {
tmp = 0;
let map1 = new Map();
for (lt = i; lt < rt + i; lt++) {
if (map1.has(a[lt])) map1.set(a[lt], map1.get(a[lt]) + 1);
else map1.set(a[lt], 1);
}
tmp = compareMaps(map1, map2);
if (tmp === b.length) answer++;
}
return answer;
}
//슬라이딩 윈도우로 b의 길이만큼 a의 부분문자열을 잡는다.
//잡은 부분문자열을 해쉬로 비교하여 아나그램을 비교한다.
//아나그램이 일치했을때부터는 들어오는 문자와 나가는 문자가 같지 않으면
//바로 넘어간다.
let a = "bacaAacba";
let b = "abc";
console.log(solution(a, b));
</script>
</body>
</html>
//강사님 코드
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<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>
</body>
</html>
반응형
'JS 알고리즘 문제풀이 > 섹션 5. 효율성(투포인터 알고리즘, 슬라이딩윈도우, 해쉬)' 카테고리의 다른 글
| 7.아나그램(Hash Map) (0) | 2022.06.20 |
|---|---|
| 6.학급 회장(Hash Map) (0) | 2022.06.18 |
| 5.최대 매출(Sliding Window) (0) | 2022.06.17 |
| 4.연속부분수열2(Two Pointers Algorithm) (0) | 2022.06.16 |
| 3.연속부분수열1(Two Pointers Algorithm) (0) | 2022.06.15 |