Inflearn Community Q&A
asked
시간복잡도 질문입니다!
Resolved
Written on
·
259
1
안녕하세요 선생님~~
강의에 나온 답안의 시간복잡도는
solution 함수의 for문 안에서 compareMaps 가 실행되고, compareMaps 또한 for문을 가지기 때문에 O(N^2) 이라고 생각했는데 맞나요??
제가 구현한 코드는 아래와 같은데요 제 코드는 확실히 O(N^2) 인 것 같습니다.. ㅠ
function solution(s, t) {
let count = 0;
let l = 0;
// 1. 부분 문자열을 구하는데, t.length와 같은 길이를 가진 문자열을 구한다.
for (let r = t.length; r <= s.length; r++) {
const temp = s.substring(l++, r);
// 2. 그 문자열이 아나그램인지 확인한다.
if (isAnagram(temp, t)) count++;
else continue;
}
return count;
}
function isAnagram(str1, str2) {
// 정렬 사용하지 않고 해보기
const map = new Map();
for (let char of str1) {
if (map.has(char)) map.set(char, map.get(char) + 1);
else map.set(char, 1);
}
for (let char of str2) {
if (!map.has(char)) return false;
if (map.has(char) && !map.get(char)) map.set(char, map.get(char) - 1);
if (map.get(char) === 0) return false;
}
return true;
}
let a = 'bacaAacba';
let b = 'abc';
console.log(solution(a, b));javascript코테 준비 같이 해요!
Quiz
What is the main reason why two-pointer or sliding window techniques are more efficient than nested loops?
Because it uses less memory?
Is it because the code is shorter?
Is it because it achieves O(N) time complexity in most cases?
Is it because it's not affected by the input data size?
Answer 2
3
codingcamp
Instructor
안녕하세요^^
네. 맞습니다. O(n)코드를 완성해 놓았는데 시간이 없어 영상을 찍지 못했습니다. 다음주 주말쯤 찍어서 올리도록 하겠습니다. 아래 코드는 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"));0
