다른 방식으로 풀어보았는데, 효율적인 코드가 맞는지 확인 부탁드리겠습니다!

Question

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")); 선생님께서 풀어주신 방식이랑 너무 달라, 이 방식도 효율적인지 확신이 안서서요. 제 코드 한 번 확인 부탁드리겠습니다.

김태원 · Answer

안녕하세요^^ 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"));