알고리즘 문제 | 빈도수세기_anagram

문제설명

2개의 문자를 인자로 받으며 두번째 문자열이 첫번째 문자열의 anagram인지 확인하는 validAnagram 함수이다. 
(서로 가지고있는 문자의 개수가 똑같은지 확인)

 

예시

str1	str2	return
aaz	zza	true
awesome	awesom	false
texttwisttime	timetwisttext	true

 

🤔 문제 풀이  (before)

function validAnagram_before(str1, str2) {
  let obj1 = {};
  let obj2 = {};

  //1. 길이 비교
  if (str1.length !== str2.length) {
    return false;
  }

  //2. str1, str2의 요소를 객체로 카운팅하기
  for (let e of str1) {
    if (obj1[e] === undefined) {
      obj1[e] = 1;
    } else {
      obj1[e] += 1;
    }
  }

  for (let e of str2) {
    if (obj2[e] === undefined) {
      obj2[e] = 1;
    } else {
      obj2[e] += 1;
    }
  }

  // obj1 { t: 5, e: 2, x: 1, w: 1, i: 2, s: 1, m: 1 }
  // obj2 { t: 5, e: 2, x: 1, w: 1, i: 2, s: 1, m: 1 }

  //3. 객체의 값 비교
  for (let e in obj1) {
    if (obj1[e] !== obj2[e]) {
      return false;
    }
  }
  return true;
}

console.log('validAnagram',validAnagram('texttwisttime', 'timetwisttext')); //true

O(n)의 시간복잡도를 가지지만, 반복문을 총 3번 사용한다.

 

---

💡 문제 풀이

function validAnagram(str1, str2) {
  //1. 길이 비교
  if (str1.length !== str2.length) {
    return false;
  }

  //2. str1의 요소를 객체로 카운팅하기
  const lookup = {};
  for (let i = 0; i < str1.length; i++) {
    let letter = str1[i];
    lookup[letter] ? (lookup[letter] += 1) : (lookup[letter] = 1);
  }
  // lookup { t: 5, e: 2, x: 1, w: 1, i: 2, s: 1, m: 1 }

  //3. str2 의 요소를 객체에서 찾아 -1을 하고 값이 0이거나, 없다면 false를 반환.
  for (let i = 0; i < str2.length; i++) {
    let letter = str2[i];
    if (!lookup[letter]) {
      return false;
    } else {
      lookup[letter] -= 1;
    }
  }

  return true;
}

console.log('validAnagram', validAnagram('texttwisttime', 'timetwisttext'));

해당 풀이는 O(n)의 시간복잡도이며,

하나의 문자열을 객체로 만들고, 그 객체의 값을 -로 빼면서 확인하는 방법을 사용하여 반복문을 총 2번 사용한다. (시간이 조금 더 짧다)