[HackerRank] Sherlock and Anagrams (Javascript)

요즘 머리 환기 겸 간간히 코딩 테스트를 연습하고 있는데 문자열 관련한 문제를 풀던 중 중요한 사실을 하나 알았다.

 

우선 문제는 다음과 같다.

 

---

문제 설명.

 

주어진 문자열의 부분 문자열 중 Anagram의 개수를 찾는 것.

 

※ Anagram: 문자열의 길이와 포함된 문자의 개수가 같은 두 문자열의 집합

 

예를 들어 'abba'이면, [a, a], [b, b], [ab, ba], [abb, bba]가 Anagram이므로 4를 리턴해야 한다.

 

출처. https://www.hackerrank.com/challenges/sherlock-and-anagrams/problem

---

아무리 머리를 싸매도 O(n^4)밖에 생각이 안나서 Brute Force로 풀었다.

 

function isAnagram (A, B) {
  let objA = {}, objB = {};
 
  for (const a of A) {
    !!objA[a] ? objA[a]++ : objA[a] = 1
  }
 
  for (const b of B) {
    !!objB[b] ? objB[b]++ : objB[b] = 1
  }
 
  return Object.keys(objA).every(key => objA[key] === objB[key])
  ? true
  : false
}
 
function compare (str, s) {
  const len = str.length;
 
  let cnt = 0;
  for (let i=0;i<=s.length-len;i++) { 
    const str2 = s.substring(i, i+len);
    if(isAnagram(str, str2)) {
      cnt++
    }
  }
 
  return cnt;
}
 
function sherlockAndAnagrams(s) {
  let result = 0;
 
  for (let i=0;i<s.length;i++) { // 시작 인덱스
    for (let e=1;e < s.length;e++) { // 비쿄할 문자 개수
      if (i+e >= s.length) continue;
      let str1 = s.substring(i, i+e); // 비교문자열 하나 선택
 
      result += compare(str1, s.substring(i+1, s.length)) // 나머지 가능성 있는 문자열들과 비교하는 함수, i+1부터 비교 시작
    }
  }
  return result
}
 
const strs = [
  "ifailuhkqqhucpoltgtyovarjsnrbfpvmupwjjjfiwwhrlkpekxxnebfrwibylcvkfealgonjkzwlyfhhkefuvgndgdnbelgruel",
  "gffryqktmwocejbxfidpjfgrrkpowoxwggxaknmltjcpazgtnakcfcogzatyskqjyorcftwxjrtgayvllutrjxpbzggjxbmxpnde",
  "mqmtjwxaaaxklheghvqcyhaaegtlyntxmoluqlzvuzgkwhkkfpwarkckansgabfclzgnumdrojexnrdunivxqjzfbzsodycnsnmw",
  "ofeqjnqnxwidhbuxxhfwargwkikjqwyghpsygjxyrarcoacwnhxyqlrviikfuiuotifznqmzpjrxycnqktkryutpqvbgbgthfges",
  "zjekimenscyiamnwlpxytkndjsygifmqlqibxxqlauxamfviftquntvkwppxrzuncyenacfivtigvfsadtlytzymuwvpntngkyhw",
  "ioqfhajbwdfnudqfsjhikzdjcbdymoecaokeomuimlzcaqkfmvquarmvlnrurdblzholugvwtkunirmnmsatrtbqlioauaxbcehl",
  "kaggklnwxoigxncgxnkrtdjnoeblhlxsblnqitdkoiftxnsafukbdhasdeihlhfrqkfzqhvnsmsgnrayhsyjsniutmgpfjmssfsg",
  "fhithnigqftuzzgpdiquhlsozksxxfreddmsmvqgfgzntphmgggszwtkcbmjsllwtukgqvpvxvmatuanbeossqwtpgzbagaukmta",
  "rqjfiszbigkdqxkfwtsbvksmfrffoanseuenvmxzsugidncvtifqesgreupsamtsyfrsvwlvhtyzgjgnmsowjwhovsmfvwuniasw",
  "dxskilnpkkdxwpeefvgkyohnwxtrrtxtckkdgnawrdjtcpzplywyxmwtemwmtklnclqccklotbpsrkazqolefprenwaozixvlxhu"
  ]
 
for (const str of strs) {
  console.log(sherlockAndAnagrams(str));
}
 
/**
399
471
370
403
428
412
472
457
467
447
 */
 
 

처음엔 가장 긴 Task인 위의 예시만 제한 시간 통과를 못해서 혹시나 Brute Force가 아닌가 싶어 걱정했는데 isAnagram함수를 for of문이 아니라 Array.every 메소드를 사용하니까 되었다.

 

Array.every 메소드는 콜백함수에서 false가 나면 그 즉시 순회를 멈추고 false를 리턴하기 때문에 단순 비교보다 더 빠르다.

 

따라서 이러한 배열 관련 메소드들을 적절한 상황에서 잘 활용하면 알고리즘 테스트 Time Limit을 더욱 잘 통과할 수 있을 거라는 걸 깨달았다.