[JS 알고리즘] 모든 아나그램 찾기 완전 정리 – 해시와 슬라이딩 윈도우 풀이

• 문제
• 해설
• 풀이
• QnA

문제

S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하는 문제입니다.
아나그램 판별 시 대소문자는 서로 다른 문자로 구분되며, 부분문자열은 반드시 연속된 문자열이어야 합니다.

첫 번째 줄에는 문자열 S가 주어지고, 두 번째 줄에는 문자열 T가 주어집니다.
S문자열의 길이는 최대 10,000을 넘지 않으며, T문자열의 길이는 S문자열의 길이보다 작거나 같습니다.

출력은 S단어 안에서 T문자열과 아나그램 관계가 되는 부분문자열의 총 개수를 출력해야 합니다.

예를 들어 S = “bacaAacba”, T = “abc”가 주어졌을 경우,
{bac}, {acb}, {cba} 총 3개의 부분문자열이 아나그램에 해당하므로 정답은 3이 됩니다.

해설

처음 이 문제를 접했을 때, 직접적인 풀이를 떠올리지 못하고 접근 방법에서 막혔습니다.
문자열을 하나하나 잘라 비교하는 방식은 떠올릴 수 있었지만, 시간 복잡도 측면에서 적절한지 판단하기 어려웠습니다.

만약 S의 모든 부분 문자열을 생성해 정렬 후 비교한다면, 문자열 길이가 커질수록 연산량이 급격히 증가합니다.
따라서 이 문제는 단순 구현 문제가 아니라, 자료구조와 알고리즘 선택이 핵심인 문제입니다.

이 지점에서 해시(Map)를 사용해 문자 빈도를 관리하고, 슬라이딩 윈도우를 통해 연속된 구간을 효율적으로 이동시키는 접근이 필요해집니다.

풀이

먼저 문제의 전체 해답 코드를 한 번에 확인한 뒤, 아래에서 단계별 코드와 함께 흐름을 나누어 설명합니다.
한 줄씩 따라가며 이해할 수 있도록 실제 코딩테스트 풀이 순서에 맞게 구성했습니다.

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;
  }
  return true;
}

function solution(s, t) {
  let answer = 0;
  let tH = new Map();
  let sH = new Map();

  for (let x of t) {
    tH.set(x, (tH.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);
  }

  let lt = 0;
  for (let rt = len; rt < s.length; rt++) {
    sH.set(s[rt], (sH.get(s[rt]) || 0) + 1);

    if (compareMaps(sH, tH)) answer++;

    sH.set(s[lt], sH.get(s[lt]) - 1);
    if (sH.get(s[lt]) === 0) sH.delete(s[lt]);
    lt++;
  }

  return answer;
}

1단계는 기준이 되는 문자열 T의 문자 빈도를 해시(Map)로 만드는 과정입니다.
이후 모든 비교는 이 해시를 기준으로 이루어집니다.

let tH = new Map();
for (let x of t) {
  tH.set(x, (tH.get(x) || 0) + 1);
}

아나그램 판별은 문자 종류와 개수가 완전히 같아야 하므로,
문자열 자체가 아니라 빈도 구조를 저장하는 것이 핵심입니다.

2단계는 슬라이딩 윈도우를 시작하기 전, S 문자열에서 미리 윈도우 크기만큼 해시를 구성하는 과정입니다.
윈도우 크기는 항상 T의 길이와 같아야 합니다.

let sH = new Map();
let len = t.length - 1;
for (let i = 0; i < len; i++) {
  sH.set(s[i], (sH.get(s[i]) || 0) + 1);
}

이렇게 하면 이후 오른쪽 포인터가 이동할 때마다,
정확히 길이가 T인 구간을 유지할 수 있습니다.

3단계부터 실제 슬라이딩 윈도우가 시작됩니다.
오른쪽 포인터를 이동시키며 새로운 문자를 해시에 추가합니다.

let lt = 0;
for (let rt = len; rt < s.length; rt++) {
  sH.set(s[rt], (sH.get(s[rt]) || 0) + 1);

  if (compareMaps(sH, tH)) answer++;

  sH.set(s[lt], sH.get(s[lt]) - 1);
  if (sH.get(s[lt]) === 0) sH.delete(s[lt]);
  lt++;
}

이 구간에서 가장 중요한 포인트는 두 가지입니다.
첫째, 해시 비교는 항상 윈도우 크기가 동일할 때만 수행됩니다.
둘째, 왼쪽 포인터에서 빠지는 문자는 반드시 정리해 주어야 합니다.

특히 빈도가 0이 된 문자를 삭제하지 않으면,
해시 크기 비교에서 오답이 발생할 수 있으므로 반드시 처리해야 합니다.

정리

이 문제는 아나그램이라는 개념보다, 연속된 부분 문자열을 어떻게 효율적으로 검사할 것인지가 핵심입니다.
해시와 슬라이딩 윈도우를 함께 사용하면 시간 복잡도를 크게 줄일 수 있으며,
문자열 관련 문제에서 매우 자주 활용되는 패턴입니다.

QnA

Q. 왜 문자열을 정렬해서 비교하면 안 되나요?
정렬 방식은 구현은 쉽지만, 매번 정렬이 발생해 시간 복잡도가 크게 증가합니다. 이 문제의 입력 크기에서는 비효율적입니다.

Q. Map 대신 객체를 사용해도 되나요?
가능하지만, 키의 개수 관리와 비교 측면에서는 Map이 더 명확하고 안전합니다.

Q. 이 패턴은 어디에 또 사용되나요?
부분 문자열, 연속 구간 합, 빈도 비교 문제 등에서 거의 동일한 구조로 반복 등장합니다.

Q. 면접에서 이 문제를 설명하라고 하면 어떻게 말해야 하나요?
해시로 문자 빈도를 관리하고, 슬라이딩 윈도우로 연속 구간을 유지하며 비교했다고 설명하면 됩니다.

Q. 시간 복잡도는 어떻게 되나요?
문자열 S를 한 번 순회하므로 O(N)이며, 해시 비교는 문자 종류 수만큼만 수행됩니다.

Q. 대소문자 조건은 왜 중요한가요?
문자 자체를 키로 사용하기 때문에 대소문자 구분 여부가 결과에 직접적인 영향을 줍니다.