[Algorithm] Frequency Counter

알고리즘 문제에서 빈도수 세기 문제의 키는 복잡도를 줄이는 일에 있다고 볼 수 있다. 많은 문제들에서 naive code는 O(n^2)이상의 복잡도를 가지게 되는데, 이 복잡도를 줄여주는 것이 문제의 요지라 할 수 있다.

Anagram problem

아나그램 문제는 문자열 비교 문제이다. 두 개의 string, 'ABCDE'와 'BEDAC'가 주어졌을 때 두 string이 같은 letter들을 가지고 있는지 비교하는 것이 대표적인 예이다. 이는 이중 반복문으로 쉽게 구현해 볼 수 있다.

for (char1 in string1){ // O(n)
  for(char2 in string2){// O(n)
    car1 ? char2 
}

이렇게 string1에서 글자를 하나씩 가지고와 string2와 대조하는 방법은 이중 반복문이 들어가므로 O(n^2)의 복잡도를 가진다. 하지만 여기서 객체의 속성에 접근할 때 O(1)의 복잡도를 가진다는 사실을 이용하면 문제의 복잡도를 크게 개선할 수 있다. string1과 string2를 객체화 하면 다음과 같이 나타낼 수 있다.

objstr1 = { A:1,B:1,C:1,D:1,E:1}
objstr2 = { A:1,B:1,C:1,D:1,E:1}

string에 있는 letter를 key로, 등장 횟수를 element로 객체를 구성하고 나면 이제 객체에 속성에 접근하는 복잡도가 O(1)임을 이용하여 O(n)의 복잡도를 가지는 솔루션을 만들 수있다.

function anagram(string1,string2){
  if (string1.legnth!==string2.length) return false
  let obj1 ={}
  let obj2 ={}
  for (let val of string1) { //objstr1 만들기
    objstr1[val] = (objstr1[val] || 0) +1
  }
  for (let val of string2){ //objstr2 만들기
    objstr2[val] = (objstr2[val] || 0) +1
  }
  for (let key in objstr1){ //객체에 접근하여 비교
    if(!(key**2 in obj)){
      return false
    }
    if(objstr2[key**2] !== objstr1[key]){
      return false
    }
  }
return true
}

복잡도는 3n에 비례하지만 O(n)의 스케일을 갖는것을 알 수 있다.

다중 포인터 패턴

정렬된 배열 [1,1,2,2,3,4,5,5,6]에서 중복을 제외한 숫자들을 세는 문제가 있다. 위 배열의 9개 숫자중에 중복을 제외하면 1,2,3,4,5,6이 있으므로 고유값의 갯수는 6개이다. 이는 아나그램 문제와 같이 각 요소들을 배열 전체와 비교하는 방법이 있을 것이다. 이 때에도 복잡도는 O(n^2)가 된다. 이 문제는 두 개의 포인터를 이용해서 O(n)의 복잡도를 갖는 솔루션을 얻을 수 있다.

 i
[1,1,2,2,3,4,5,5,6]
   j

두개의 포인터 i와 j를 두고 j를 키우면서 i인덱스의 요소와 비교하는 방법이다. 이때 j번째 인덱스가 i번째 인덱스와 다른경우

 i
[1,1,2,2,3,4,5,5,6]
     j

i+1인덱스에 j번째 인덱스의 요소를 넣는 방법을 취한다.

   i
[1,2,2,2,3,4,5,5,6]
     j

이를 배열 끝까지 반복하면 아래와 같은 배열을 얻을 수 있다.

           i
[1,2,3,4,5,6,5,5,6]
                 j

이제 길이가 i+1인 배열을 얻을 수 있다.

function countUniqueValues(arr) {
  let i = 0
  for (let j = 1; j < arr.length; j++) {
    if (arr[i] !== arr[j]) {
      i++
      arr[i] = arr[j]
    }
  }
}