문제
S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하 세요. 아나그램 판별시 대소문자가 구분됩니다. 부분문자열은 연속된 문자열이어야 합니다.
[입력설명]
첫 줄에 첫 번째 S문자열이 입력되고, 두 번째 줄에 T문자열이 입력됩니다.
S문자열의 길이는 10,000을 넘지 않으며, T문자열은 S문자열보다 길이가 작거나 같습니다.
[출력설명]
S단어에 T문자열과 아나그램이 되는 부분문자열의 개수를 출력합니다.
입력예제 1
bacaAacba abc
출력예제 1
3
출력설명: {bac}, {acb}, {cba} 3개의 부분문자열이 "abc"문자열과 아나그램입니다.
문제 풀이
예습 이론
- 해시: 아나그램
- 투포인터: 부분 문자열
- 슬라이딩 윈도우: 연속된 문자열
코드
- 이 문제는 해시, 투포인터, 슬라이딩 윈도우를 사용한 문제다. 앞의 예제 7개를 총집합한 보스 문제라고 보면될듯!!!(해시: 아나그램 / 투포인터: 부분 문자열 / 슬라이딩 윈도우: 연속된 문자열)
- 풀이 과정
자바스크립트는 파이썬과 달리 해시맵을 비교하는 내장함수가 없다. 따라서, 해시맵을 비교하는 함수를 직접 작성해준다. (compareMaps 함수)
<html>
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
//sH, tH를 비교하는 함수(파이썬에는 내장함수 있음, js에는 없어서 직접 만들어야해...)
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; //map1의 key가 map2에 없을 때, false 리턴 || map2.get(key): map2의 value값, val: map1의 value값
}
return true;
//console.log(map1.size);
}
function solution(s, t){
let answer=0;
let tH = new Map();
let sH = new Map();
//t의 해쉬맵 만들어줌
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;
//len전까지 s의 해쉬맵 만들어줌
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;
//len부터 s의 해쉬맵 만듦
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); //rt위치에있는 문자열 추가한 직후,
if(compareMaps(sH, tH)) answer++; //(1)sH, tH가 같은지 비교하고, 같으면 answer++
sH.set(s[lt], sH.get(s[lt])-1); //(2)슬라이딩 윈도우! 현재 lt값 빼줌(-1)
if(sH.get(s[lt])===0) sH.delete(s[lt]); //(만약, 빼줄 값이 없다면(0이라 -1을 할 수 없으면) delete)
lt++;
}
return answer;
}
let a="bacaAacba";
let b="abc";
console.log(solution(a, b));
</script>
</body>
</html>
내가 짱이다 😎 매일 조금씩 성장하기🌱
2개의 댓글
2021년 9월 13일
9/13
1. 해쉬맵끼리 같은지 비교하는 함수 작성(파이썬은 해쉬맵 비교 내장함수 있지만, 자바스크립트는 없기 때문에 직접 작성해줘야함)
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; //map1의 key가 map2에 없을 때, false 리턴 || map2.get(key): map2의 value값, val: map1의 value값
}
return true;
}- lt 사용하기
- map에서 for of 구문 쓸 때, for(let [key, val] of map)과 같이 사용할 것! key:val 하나의 쌍이다. 주의 또 주의 또 주의 또 주의!!!
답글 달기
9/12
1. 문자 + 문자는 되지만, 문자 - 문자는 안된다.
즉, 'ab'+'a'='aba'이지만, 'ab'-'a'=NaN이다.
2. map에서 for of 구문 쓸 때, for(let [key, val] of map)과 같이 사용할 것! 주의 또 주의!