[JS] 코딩 테스트 문제 : 모든 아나그램 찾기 [해쉬, 투포인터, 슬라이딩 윈도우]

문제 : 모든 아나그램 찾기(해쉬, 투포인터, 슬라이딩 윈도우)

문제 설명

S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 프로그램을 작성하
세요. 아나그램 판별시 대소문자가 구분됩니다. 부분문자열은 연속된 문자열이어야 합니다.

▣ 입력설명

첫 줄에 첫 번째 S문자열이 입력되고, 두 번째 줄에 T문자열이 입력됩니다.
S문자열의 길이는 10,000을 넘지 않으며, T문자열은 S문자열보다 길이가 작거나 같습니다.

▣ 출력설명

S단어에 T문자열과 아나그램이 되는 부분문자열의 개수를 출력합니다.

▣ 입력예제 1

'bacaAacba'
'ab '

▣ 출력예제 1

3

출력설명: {bac}, {acb}, {cba} 3개의 부분문자열이 "abc"문자열과 아나그램입니다.

내코드

// 두 Map 아나그램 여부 확인 함수
function compareMaps(mapS, mapT) {
  let result = true;

  // mapT 길이 만큼 순회하며 mapT 의 key 를 기준으로 mapS 에도 같은 key 와 value 값을 가졌는지 확인하여 다를시 false 값을 저장
  mapT.forEach((value, key) => {
    if (mapS.get(key) === undefined || value !== mapS.get(key))
      result = false;
  });

  return result;
}

function solution(s, t) {
  let answer = 0;
  let answerArray = []; // 부분 문자열 확인용 배열
  let lt = 0;
  let mapS = new Map();
  let mapT = new Map();

  // 문자열 t 를 mapT 로 세팅
  for (const word of t) {
    mapT.has(word)
      ? mapT.set(word, mapT.get(word) + 1)
      : mapT.set(word, 1);
  }

  // 문자열 s 를 순회
  for (let i = 0; i < s.length; i++) {
    // 현재 인덱스 문자를 mapS 에 추가
    mapS.has(s[i])
      ? mapS.set(s[i], mapS.get(s[i]) + 1)
      : mapS.set(s[i], 1);

    // 최소 t 문자열 길이보다 초과해서 반복문이 진행된 이후 lt 번째 문자의 내용을 제외
    if (i >= t.length) {
      mapS.set(s[lt], mapS.get(s[lt]) - 1);
      lt++;
    }

    // 최소 t 문자열 길이 이상으로 진행된 이후 아나그램 여부 확인해 정답배열에 저장
    if (i >= t.length - 1 && compareMaps(mapS, mapT)) {
      answerArray.push(s.slice(lt, i + 1));
      answer++;
    }
  }

  console.log(answerArray);
  return answer;
}

let a = "bacaAacba";
let b = "abc";
console.log(solution(a, b));

풀이

1. 문자열 t 를 Map 으로 변환해서 mapT 로 저장
2. 문자열 s 를 순회하면서 최소 t 문자열 길이 만큼의 값 만큼만 mapS 로 저장 및 변경해가며 진행
3. mapT 와 mapS 를 비교하여 아나그램 여부를 boolean 값으로 리턴하는 함수로 처리하여 아나그램인 경우 결과 배열에 추가

보완할 수 있는 부분

// 기존코드
for (let i = 0; i < s.length; i++) {
  // 현재 인덱스 문자를 mapS 에 추가
  mapS.has(s[i])
    ? mapS.set(s[i], mapS.get(s[i]) + 1)
    : mapS.set(s[i], 1);

  // 최소 t 문자열 길이보다 초과해서 반복문이 진행된 이후 lt 번째 문자의 내용을 제외
  if (i >= t.length) {
    mapS.set(s[lt], mapS.get(s[lt]) - 1);
    lt++;
  }

  // 최소 t 문자열 길이 이상으로 진행된 이후 아나그램 여부 확인해 정답배열에 저장
  if (i >= t.length - 1 && compareMaps(mapS, mapT)) {
    answerArray.push(s.slice(lt, i + 1));
    answer++;
  }
}

// 보완코드
let len = t.length - 1;

// 최소 t 문자열 길이 - 1 만큼 mapS 를 채우고 시작
for (let i = 0; i < len; i++) {
  mapS.has(s[i])
    ? mapS.set(s[i], mapS.get(s[i]) + 1)
    : mapS.set(s[i], 1);
}

for (let i = len; i < s.length; i++) {
  // 현재 인덱스 문자를 mapS 에 추가
  mapS.has(s[i])
    ? mapS.set(s[i], mapS.get(s[i]) + 1)
    : mapS.set(s[i], 1);

  // 아나그램 여부 확인해 정답배열에 저장
  if (compareMaps(mapS, mapT)) {
    answerArray.push(s.slice(lt, i + 1));
    answer++;
  }

  // lt 번째 문자의 내용을 제외
  mapS.set(s[lt], mapS.get(s[lt]) - 1);
  lt++;  
}

보완점

기존 코드와 달리 mapS 를 mapT 길이만큼 채우고 진행하여 반복문에 불필요한 if 문 제거

---

참고

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/dashboard