문제 해결 패턴

1. Frequency Counter
2. Multiple Pointers
3. Sliding Window
4. Divide and Conquer
5. Dynamic Programming
6. Greedy Algorithms
7. Backtracking
   등등...

✔️ 1. Frequency Counter

1. object 또는 data set를 이용해서 다양한 값과 빈도를 수집
2. 서로 비슷한 값으로 구성 되어 있는지,
   서로 간의 애너그램(서로 같은 철자로 구성된건지),
   값이 다른 값이 포함되는지 여부,
   두 개 이상 또는 특정하게 발생하는 빈도 확인
3. 배열과 문자열의 중첩 루프 또는 O(N^2) 연산을 대신할 수 있음

💻 예제 1

두 배열을 받아 , 요소의 갯수가 같으면서 두번째 인자의 배열이 첫번째 인자의 배열의 제곱의 값을 갖고 있는 함수 same을 작성하시오.
(단, 순서는 상관 없다.)

same([1,2,3],[4,1,9]); // true
same([1,2,3],[1,9]); // false
same([1,2,1],[4,4,1]); // false (must be same frequency)

🔎 내가 했던 풀이

const same = (arr1, arr2) => {
  // 배열의 크기가 같지 않으면 비교 할 필요 없이 return false
  if (arr1.length !== arr2.length) return false;
  // arr1 배열 순회
  for (const arr1Elem of arr1) {
    //arr1 요소의 인덱스
    const idx = arr2.indexOf(Math.pow(arr1Elem, 2));
    if (idx > -1) {
      // 인덱스가 있으면 arr2에서 제거해서 중복으로 확인 되는 것 방지
      arr2.splice(idx, 1);
    } else {
      //없으면 바로 false 리턴
      return false;
    }
  }
  return true; //모든 조건 만족하면 true
  //
};


//문제 예제의 케이스의 답은 만족 하므로 큰 배열의 값으로 한번 더 테스트
const t1 = performance.now();
console.log(
  same(
    [
      1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100, 1, 2,
      3, 4, 5, 6, 7, 8, 9, 10, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100,
    ],
    [
      1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 10000, 1, 4, 9, 16, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 10000, 25, 36, 49,
      64, 81, 100, 10000, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 10000,
    ]
  )
);
const t2 = performance.now();
console.log(`same 걸린 시간 : ${(t2 - t1) / 1000}s`);
//same 걸린 시간 : 0.010898541000000008s

뭔가 문제 없이 잘 돌아간다. 뭔가 중첩 루프도 없어보였다.

하지만.. 위의 해결책의 경우 하나의 for문을 사용한 것 같지만 그 자체가 loop인 indexOf를 사용했다.

게다가 배열의 splice 메서드 또한 요소가 마지막에 있다면 constant time인 O(1)의 시간 복잡도를 가지지만, 요소가 중간이나 앞에 있다면 linear time O(n) 의 시간 복잡도를 가진다.

위의 해답은 시간복잡도 = O(N^2)의 복잡도를 가지게 된다...

🔎 Frequency Conter 이용한 답 => 시간복잡도 O(n)

• 두 개의 중첩 루프보다 개별 루프가 낫다

객체를 사용
: 객체를 사용하여 구성하는 것은 배열이나 문자열의 내용을 분석하는 방법으로 두 개의 배열을 객체로 세분화 하여 각 배열의 요소들 분류 후 각 배열을 비교 가능하다

const same = (arr1, arr2) => {
  if (arr1.length !== arr2.length) return false;
  // 중첩 for루프 없이 개별 배열의 빈도수를 count
  const frequencyCounter1 = {};
  const frequencyCounter2 = {};
  for (const val of arr1) {
    frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1;
  }
  for (const val of arr2) {
    frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1;
  }
  for (const key in frequencyCounter1) { 
    // 객체의 키로 접근하는 것은 O(1)의 시간 복잡도를 가진다!
    // 제곱이 되는 값이 있는지 먼저 확인
    if (!(key ** 2 in frequencyCounter2)) return false;
    
    //제곱의 값이 있다면 서로 그 갯수가 동일한지 확인
    if (frequencyCounter2[key ** 2] !== frequencyCounter1[key]) return false;
  }

  return true;
};

const t3 = performance.now();
console.log(
  same(
    [
      1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100, 1, 2,
      3, 4, 5, 6, 7, 8, 9, 10, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100,
    ],
    [
      1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 10000, 1, 4, 9, 16, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 10000, 25, 36, 49,
      64, 81, 100, 10000, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 10000,
    ]
  )
);
const t4 = performance.now();
console.log(`same 걸린 시간 : ${(t4 - t3) / 1000}s`); 
//same 걸린 시간 : 0.000051708000000004974s

객체는 순서 없는 데이터 집합으로 key값으로 접근한다 따라서 키를 통해 값에 접근 하는 것은 O(1)의 시간을 가지므로 배열을 순회하는 것 보다 더 시간이 적다.

수행시간 비교하면 내가 했던 방식은 약 0.0108985s
frequency counter 사용 시 약 0.0.0000517s 입력 값의 배열의 크기가 클 수록 시간 차이가 컸다.

💻 예제 2

두 개의 문자열을 받아 서로의 애너그램인지 확인 후 true/false 리턴하는 함수 validAnagram을 작성하시오

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

🔎 내가 했던 풀이

const validAnagram = (str1, str2) => {
  //문자열의 길이가 다르다면 비교 할 필요 없이 false 리턴
  if (str1.length !== str2.length) return false;
  // 빈문자열끼리는 true
  if (str1 === '' && str2 === '') return true;

  const str1Counter = {};
  const str2Counter = {};

  //각각 str1과 str2의 문자열 안의 글자 수의 빈도수를 각각의 object에 할당
  for (const char of str1) {
    str1Counter[char] = (str1Counter[char] || 0) + 1;
  }
  for (const char of str2) {
    str2Counter[char] = (str2Counter[char] || 0) + 1;
  }

  // 서로 객체 키가 다르면 서로의 애너그램이 될 수 없으므로 false 리턴
  for (const char in str1Counter) {
    if (str1Counter[char] !== str2Counter[char]) {
      return false;
    }
  }
  return true;
};

중첩 루프를 사용하지 않으면서 시간 복잡도 O(n)의 방식으로 해결 했다. 하지만 리팩토링 필요

• count를 위한 obejct 하나만 선언
• 해당 char이 존재하는 지 확인, 만약 이미 count 된 경우는 -1
  : 갯수가 같다면 0이 된다 그 이후 동일 문자가 있다면 if (!strCounter[char]) 에서 0값, 즉 true가 되므로 false리턴하게된다

const validAnagramRefact = (str1, str2) => {
  if (str1.length !== str2.length) return false;
  if (str1 === '' && str2 === '') return true;
  const strCounter = {};
  for (const char of str1) {
    strCounter[char] ? (strCounter[char] += 1) : (strCounter[char] = 1);
  }
  for (const char of str2) {
    if (!strCounter[char]) {
      return false;
    } else {
      strCounter[char] -= 1;
    }
  }
  return true;
};

후자의 코드가 불필요한 object 추가 선언 없이 더 깔끔해 보인다.🤓