인프런 커뮤니티 질문&답변
작성한 질문수
다른 방식으로 풀어보았는데, 효율적인 코드가 맞는지 확인 부탁드리겠습니다!
작성
·
288
0
function solution(s: string, t: string) {
let answer = 0;
t = t.split("").sort().join("");
for (let i = 0; i < s.length; i++) {
const slideStr = s.slice(i, i + t.length);
console.log(slideStr);
if (slideStr.split("").sort().join("") === t) answer++;
}
return answer;
}
console.log(solution("bacaAacba", "abc"));선생님께서 풀어주신 방식이랑 너무 달라, 이 방식도 효율적인지 확신이 안서서요. 제 코드 한 번 확인 부탁드리겠습니다.
답변 1
1
김태원
지식공유자
안녕하세요^^
slice 문도 하나의 반복문이 실행된다고 생각하셔야 합니다. 그리고 slice한 결과를 매번 sort를 하는 것도 시간을 많이 잡아먹는 것 같습니다. 영상의 방법도 시간을 많이 잡아먹는 방식인도 그래도 해쉬를 사용해서 매번 sort는 하지 않는게 좋습니다. 그리고 영상의 방법보다 더 좋은 방식은 아래 코드입니다.
아래 코드는 시간복잡도가 O(n)입니다. 스스로 분석해 보세요.
function solution(s, t){
let answer=0;
let sH = new Map();
for(let x of t){
sH.set(x, (sH.get(x) || 0)-1);
}
let len=t.length-1;
for(let i=0; i<len; i++){
sH.set(s[i], (sH.get(s[i]) || 0)+1);
if(sH.get(s[i])===0) sH.delete(s[i]);
}
let lt=0;
for(let rt=len; rt<s.length; rt++){
sH.set(s[rt], (sH.get(s[rt]) || 0)+1);
if(sH.get(s[rt])===0) sH.delete(s[rt]);
if(sH.size===0) answer++;
sH.set(s[lt], (sH.get(s[lt]) || 0)-1);
if(sH.get(s[lt])===0) sH.delete(s[lt]);
lt++;
}
return answer;
}
console.log(solution("bacacbcba", "abc"));