문제 해결 패턴

February 07, 2022

Frequency counter

O(n)의 복잡도를 가짐 어떤 상황에서 유용할까?

ex)두 배열을 입력으로 받고, 두번 째 배열이 첫 번째 배열의 값들을 각각제곱한 값을 가지고 있는지 확인하는 함수

same([1,2,3],[1,4,9])//true
same([1,2,3],[1,3,3])//false

위와 같은 경우 이중 반복문으로 확인하게 되면 O(n^2)만큼의 시간복잡도를 가지게된다. 때문에 순서가 상관이 없다면 빈도수를 확인하는게 시간 복잡도 측면에서 이득이다.

에나그램 문자를 체크하는 함수를 빈도수 카운팅을 이용해서 작성하시오.

//내가 작성한 함수.
function validAnagram(wordA, wordB) {
  const charCounterA = {}
  const charCounterB = {}
  for (let char of wordA) {
    charCounterA[char] = charCounterA[char] ? charCounterA[char] + 1 : 1
  }

  for (let char of wordB) {
    charCounterB[char] = charCounterB[char] ? charCounterB[char] + 1 : 1
  }

  for (let char of wordA + wordB) {
    if (charCounterA[char] !== charCounterB[char]) return false
  }

  return true
}

function validAnagram(first, second) {
  //더 효율적인 함수.
  const lookup = {}

  if (first.length !== second.length) return false

  for (let i = 0; i < first.length; i++) {
    const letter = first[i]
    lookup[letter] = lookup[letter] ? lookup[letter]++ : 1
  }

  for (let i = 0; i < second.length; i++) {
    const letter = second[i]
    if (!lookup[letter]) return false
    else lookup[letter]--
  }

  return true
}

two pointer

array 등을 서칭할 때 참조할 수 있는 index를 2개 이상 두는 패턴

예제 정렬된 수의 배열을 받아 두 수의 합이 0이 되는 첫 쌍을 반환하는 함수를 작성하여라 쌍이 없다면 undefined

sumZero([-3, -2, -1, 0, 1, 2, 3]) //[-3,3]
sumZero([-1, 2, 3]) //undefined;

//내가 처음 작성한 코드 투포인터의 장점을 사용하지 못했다. O(N^2)이 든다.
function sumZero(arr) {
  //두개의 index를 둔다.
  //왼쪽에서 하나의 수를 선택한다
  // 오른쪽에서 왼쪽의 수보다 큰 값들을 확인하면서 0이 되는 값이 있는지 확인한다
  // 왼쪽의 idx까지 왔다면 왼쪽의 포인터를 이동한다
  // 왼쪽 포인터가 0 이상이라면 반환

  let left = 0
  while (arr[left] <= 0) {
    let right = arr.length - 1
    while (0 <= arr[right]) {
      if (arr[left] + arr[right] === 0) return [arr[left], arr[right]]
      else right--
    }
    left++
  }

  return
}

//O(N)
function sumZero(arr) {
  let left = 0
  let right = arr.length - 1
  while (left < right) {
    const sum = arr[left] + arr[right]
    if (sum === 0) return [arr[left], arr[right]]
    else if (sum < 0) left++
    else right--
  }

  return
}

예제 2 ) 2포인터를 이용해 정렬된 배열 안에 몇 개의 고유한 번호가 있는지 반환하는 함수를 작성해라

function countUniqueValues(arr) {
  let first = 0
  let second = 1

  if (!arr.length) return 0

  while (second < arr.length) {
    if (arr[first] === arr[second]) {
      second++
    } else {
      first++
      arr[first] = arr[second]
      second++
    }
  }
  return first + 1
}