[HackerRank][Javascript] Sherlock and Anagrams

문제 - Sherlock and Anagrams

문제 설명

입력된 문자열에서 발생하는 모든 Anagram의 수를 반환하는 문제

• 이 문제는 Map을 쓰지 않고 풀었다가 한참을 고생한 문제이다. Map의 성능을 체감하게 된 문제이다.
• 일반 배열로 풀게 되면 time limit이 더 많이 걸리게 되는 것 같다.

1. 우선 반복문을 돌리기 위해 입력된 문자열을 배열로 만든다.
2. 자른 문자열의 개수를 저장하기 위해 Map을 새로 선언한다.
3. makeSubList는 len이라는 인자를 받아 해당 숫자만큼 자르고 정렬해 개수를 앞서 만든 Map에 저장한다.
   이 때, makeSubList가 reduce 안에서 불려서 바로 계산되기 때문에 함수 시작 부분에서 .clear()를 통해 Map을 비워준다.
4. isAnagram에서는 makeSubList 함수에서 만들어진 Map을 바탕으로 Anagram의 개수를 센다.

• Anagram의 개수를 세는 방법인 (curr * (curr - 1)) / 2은 규칙을 바탕으로 만들어진 것이다.

s가 kkkk일 때 잘린 문자열, 중복 개수, 애나그램 개수는 아래 표와 같다.
애나그램 개수는 위의 식과 같은 규칙을 가지고 있어 계산식으로 간단하게 풀 수 있다.

잘린 문자열	중복 개수	애나그램 개수
k	4	( 4 * (4 - 1) ) / 2 = 6
kk	3	( 3 * (3 - 1) ) / 2 = 3
kkk	2	( 2 * (2 - 1) ) / 2 = 1

성공 코드

function sherlockAndAnagrams(s) {
  const sList = s.split(""); // 1
  let mapOfSub = new Map(); // 2

  const makeSubList = (len) => {
    // 3
    mapOfSub.clear();
    sList.forEach((ss, i) => {
      const splitStr = s.substring(i, i + len);
      const sortStr = splitStr.split("").sort().join("");
      if (sortStr.length === len) {
        mapOfSub.has(sortStr)
          ? mapOfSub.set(sortStr, mapOfSub.get(sortStr) + 1)
          : mapOfSub.set(sortStr, 1);
      }
    });
  };

  const isAnagram = (len) => {
    // 4
    makeSubList(len);
    return [...mapOfSub.values()].reduce((prev, curr) => prev + (curr * (curr - 1)) / 2, 0);
  };

  return sList.reduce((prev, curr, currIndex) => {
    if (!currIndex) return prev + 0;
    return prev + isAnagram(currIndex);
  }, 0);
}