투포인터 없이 풀어 봤는데 반례라거나 시간복잡도의 문제가 있을까요... - 인프런

function isSame(map1, map2) {
        if (map1.size !== map2.size) return false;
        for (const [key, val] of map2) {
          if (!map1.has(key) || map1.get(key) !== val) return false;
        }

        return true;
      }

      function solution(s, t) {
        let answer = 0;
        const map1 = new Map();
        const map2 = new Map();
        const n = t.length;

        const ss = s.slice(0, n);

        for (const s of t) {
          if (map1.has(s)) {
            map1.set(s, map1.get(s) + 1);
          } else {
            map1.set(s, 1);
          }
        }

        for (const s of ss) {
          if (map2.has(s)) {
            map2.set(s, map2.get(s) + 1);
          } else {
            map2.set(s, 1);
          }
        }

        if (isSame(map1, map2)) answer++;

        for (let i = n; i < s.length; i++) {
          map2.delete(s[i - n]);
          map2.set(s[i], map2.get(s[i]) ? map2.get(s[i]) - 1 : 1);

          if (isSame(map1, map2)) answer++;
        }

        return answer;
      }

      const s = "bacaAacba";
      const t = "abc";
      console.log(solution(s, t));

슬라이딩 윈도우로 처음 t만큼 잘라서 비교한 이후 부터 돌면서 처리 했는데 다른 문제가 있을까요...?

안녕하세요, 인프런 AI 인턴입니다.

shut up and squat님, 제시하신 자바스크립트 코드를 살펴보았을 때, 몇 가지 개선점이 보입니다. 코드의 목적은 문자열 s에서 문자열 t에 있는 문자들의 순열과 일치하는 부분 문자열의 개수를 찾는 것으로 보입니다.

map2.delete(s[i - n]); 부분에서는 맵에서 문자를 삭제하기 전에 해당 문자의 개수를 확인하고 개수가 1이상이면 개수를 줄이고, 1이라면 삭제해야 합니다. 그렇지 않으면 문자가 여러 번 등장했을 경우 정상적인 개수 파악이 어렵습니다.
map2.set(s[i], map2.get(s[i]) ? map2.get(s[i]) - 1 : 1); 코드에서는 새로운 문자를 맵에 추가하는 부분입니다만, - 1이 아닌 + 1이 되어야 합니다. 새로 추가되는 문자의 개수를 증가시켜야 하기 때문입니다.

수정된 부분을 반영하면 코드는 다음과 같이 변경될 수 있습니다:

// 지금 보여주신 부분은 그대로 두고, 다음 부분만 변경하겠습니다.

for (let i = n; i < s.length; i++) {
  if (map2.get(s[i - n]) > 1) {
    map2.set(s[i - n], map2.get(s[i - n]) - 1);
  } else {
    map2.delete(s[i - n]);
  }
  
  // ... 나머지 코드는 그대로이며, 아래 부분만 변경합니다.
  
  map2.set(s[i], map2.has(s[i]) ? map2.get(s[i]) + 1 : 1);

  // ... 나머지 코드는 그대로입니다.
}

이렇게 변경하면, 문자를 적절하게 추가하고 삭제하는 동작이 올바르게 수행되어 올바른 답을 얻을 수 있을 것입니다. 시간 복잡도 측면에서 투 포인터 알고리즘과 비교해도 이 알고리즘은 O(N)이므로 큰 문제가 없어 보입니다.

참고하셔서 문제를 해결하는 데 도움이 되셨으면 합니다. 추가적인 질문이나 궁금한 점이 있다면 언제든지 문의해 주세요.

인프런 커뮤니티 질문&답변

투포인터 없이 풀어 봤는데 반례라거나 시간복잡도의 문제가 있을까요...?