[알고리즘] 아나그램 알고리즘 (anagram)

카테고리 : 컴퓨터 공학
태그: cs · 컴퓨터 공학 · algorithm · Frequency Counter · 빈도수 세기 · Refactored · anagram · 아나그램 알고리즘

1. 아나그램 알고리즘 (anagram)

문제 설명

  • validAnagram이라는 함수는 두 문자열을 파라미터로 받아서 두 문자열이 애너그램 관계인지 확인하여 true, false를 반환하는 함수

제한사항

  1. 알파벳은 소문자인 경우만 고려할 것

2. My Solution

1) sort() 함수 활용

  • validAnagram 함수에 문자열 두개를 매개변수로 받아와서 두개의 문자를 비교함
  • sortingString 함수에 매개변수의 문자열을 Spread Opertor로 배열로 변환함
  • toLowerCase() 메서드로 알파벳은 소문자로 통합 비교
  • sort() 메서드로 배열들을 오름차순 정렬 시킴
  • join() 메서드로 다시 하나의 문자열로 만듬
const validAnagram = (string1, string2) => {
  return sortingString(string1) === sortingString(string2);
};

const sortingString = (string) => {
  return [...string.toLowerCase()].sort().join("");
};

시간 복잡도 O(n log n)

  • sortingString 함수 = string을 소문자로 변환한 다음, 배열로 만들고 정렬한 뒤 다시 문자열로 변환함
  • validAnagram 함수 = validAnagram 함수의 시간 복잡도는 2 * O(n log n) 상수 계수는 시간 복잡도 표기에서 일반적으로 무시

3. Insight Solution

1) 두개의 loop 를 사용 (시간 복잡도를 O(n)으로 유지할 수 있다.)

function validAnagram(first, second) {
  //두 문자열의 길이를 비교하여 길이가 다르다면 바로 false를 반환
  if (first.length !== second.length) {
    return false;
  }

  const lookup = {};

  for (let i = 0; i < first.length; i++) {
    let letter = first[i];
    // 첫 번째 문자열 first를 반복하면서 각 문자를 lookup 객체에 저장합니다. 이미 저장된 문자라면 해당 문자의 개수를 1 증가시키고, 처음 나타나는 문자라면 개수를 1로 설정
    lookup[letter] ? (lookup[letter] += 1) : (lookup[letter] = 1);
  }
  console.log(lookup);

  // 두 번째 문자열 second를 반복하면서 각 문자를 확인합니다. 만약 해당 문자가 lookup 객체에 없거나 개수가 0이라면, 아나그램이 아니므로 false를 반환
  for (let i = 0; i < second.length; i++) {
    let letter = second[i];
    //만약 해당 문자가 lookup 객체에 존재하고 개수가 1 이상이라면, 해당 문자의 개수를 1 감소
    if (!lookup[letter]) {
      return false;
    } else {
      lookup[letter] -= 1;
    }
  }
  //두 번째 문자열의 모든 문자를 확인한 후에도 문제가 없다면, 두 문자열은 아나그램이므로 true를 반환합니다.
  return true;
}

// {a: 0, n: 0, g: 0, r: 0, m: 0,s:1}
validAnagram("anagrams", "nagaramm");

시간 복잡도 O(N) : 객체를 사용

4. Refactored Solution

1) 두개의 loop 를 사용 (시간 복잡도를 O(n)으로 유지)

const validAnagram = (string1, string2) => {
  if (string1.length !== string2.length) {
    return false;
  }
  let stringObj1 = {};
  let stringObj2 = {};

  for (let val of string1) {
    stringObj1[val] = (stringObj1[val] || 0) + 1;
  }
  for (let val of string2) {
    stringObj2[val] = (stringObj2[val] || 0) + 1;
  }

  for (let key in stringObj1) {
    if (!stringObj2[key]) {
      return false;
    }
    if (stringObj1[key] !== stringObj2[key]) {
      return false;
    }
  }
};
  • in 연산자; ****명시된 key값이 명시된 객체에 존재하면 true 반환
  • for..of 객체의 모든 열거할 수 있는 item의 개수만큼 반복
  • for..in 키가 지정된 모든 열거 가능한 key에 대해 반복

시간 복잡도 O(N) : Nested loop가 아닌 두개의 loop 를 사용