[알고리즘] 빈도수 세기 패턴

빈도수 세기 패턴?

어떠한 문자열 및 배열을 빈도수체크 방식으로 풀이함

방식

원래는 중첩 for문을 이용하여 풀이하였지만
시간복잡도에서 O(n^2)의 시간 복잡도를 보였기 때문에,
효율적인 알고리즘이 아니라고 판단하였고
빈도수 세기 패턴을 이용하여 시간 복잡도를 줄였다.

문제

두 개의 문자열이 주어졌을 때, 두 번째 문자열이 첫 번째 문자열의 애너그램인지 확인하는 함수를 작성합니다. 애너그램은 다른 글자의 글자를 재배열하여 형성된 단어, 구 또는 이름입니다.

예시

validAnagram('', '') // true
validAnagram('aaz', 'zza') // false
validAnagram('anagram', 'nagaram') // true
validAnagram("rat","car") // false) // false
validAnagram('awesome', 'awesom') // false
validAnagram('amanaplanacanalpanama', 'acanalmanplanpamana') // false
validAnagram('qwerty', 'qeywrt') // true
validAnagram('texttwisttime', 'timetwisttext') // true

풀이 코드

function validAnagram(str1,str2){
  // 두 문자열의 길이가 다르다면 false
    if(str1.length !== str2.length){
        return false;
    }
     // 새로운 객체 생성
    let lookup = {};

      // 객체에 값 할당
      // 할당시 key가 비어있다면 count 0
      // key 존재할 시, count 하나씩 올리는 로직
    for(let val of str1){
        lookup[val] = (lookup[val] || 0) + 1
    }

      // lookup 객체와 str2을 비교하여 계산
      // 존재하지 않는다면 false
    for(let val of str2){
        if(!lookup[val]){
            return false
        } else {
            lookup[val] -= 1;
        }
    }

      // 모든 if문 통과시, true를 return
    return true;
}

이런 식으로 for루프를 중첩시키지 않도록 하여 조금더 효율적인 알고리즘을 구현할 수 있다.