알고리즘 - 문제 해결 패턴

문제 해결을 패턴 파악하기

Intro

I. 빈도수 세기 패턴

데이터와 입력값이 서로 비슷한 값인지, 해당 범위의 값을 동일하게 가지고 있는지 등을 측정하는 문제가 빈도수 세기 패턴의 문제입니다.

I-I. 빈도수 세기 패턴 기본
  1. 2개의 배열을 인자로가지는 same함수를 작성합니다. 두 배열은 같은 길이를 가지며 두 번째 배열은 첫 번째 배열의 인자의 제곱인 수를 가지고 있어야 합니다. 단, 중복되선 안됩니다.
js
same([1,2,3], [4,1,9]) // true
same([1,2,3], [1,9]) // false
same([1,2,1], [4,4,1]) // false

우선 다음과 같이 풀이할 수 있습니다.

js
function same(arr1, arr2){
  // 같은 길이인지 확인
  if(arr1.length !== arr2.length){
    return false;
  }
  //
  for(let i = 0 ; i < arr1.length; i++){ // n
    // 첫번째 인자의 제곱이 두번째 인자가 가지고 검사
    let correctIndex = arr2.indexOf(arr[i] ** 2) // n
    // 가지고 있지 않다면 false
    if(correctIndex === -1) {
      return false;
    }
    // 가지고 있는 경우 두번째 인자에서 해당 인덱스 제거
    arr2.splice(correctInfex, 1)
  }
  return true;
}

우선 위와 간단히 풀이할 수 있습니다. 시간복잡도 수치로 표기하면 O(n²)와 같습니다.

js
same([1,2,3,2], [9,1,4,4])

function same(arr1, arr2){
  if(arr1.length !== arr2.length){
    return false;
  }
  let frequencyCounter1 = {}
  let frequencyCounter2 = {}
  // 2n
  for(let val of arr1){
    // [1, 2, 1]
    frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1
  }
  for(let val of arr2){
    // [1, 2, 1]
    frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1
  }
  for(let key in frequencyCounter1){ // 첫번째 객체의 키 열거
    // 키 비교
    if(!(key in frequencyCounter1)){
      // 해당 키의 제곱을 두번째 배열이 키로 가지고 있지 않다면 false
      if(!(key ** 2 in frequencyCounter2)){
        return false;
      }
      // 같은 반복 횟수를 가지고 있는지 검사 가지고 있지 않다면 false
      if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
        return false;
      }
    }
    return true;
  }
}

위와 같이 수정해서 3n으로, O(n)의 수치가 나오도록 수정할 수 있습니다.

I-II. 예시 문제 - 에너그램

두 개의 문자열을 취하며 두 문자열이 서로의 에너그램이면 참이 반환됩니다. 문제 해결은 O(n)이어야 합니다.

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

패턴은 비슷하게 적용할 수 있습니다. 객체를 선언한 후 해당 객체에 담긴 빈도를 다른 인자와 비교하면 됩니다.

js
validAnagram('anagram', 'nagaram'); // true

function validAnagram(first, second) {
  // 길이 비교
  if(first.length !== second.length) {
    return false
  }

  const lookup = {};
  // 서로 같은 값을 가지고 있는지 검사
  for(let i = 0 ; i < first.length ; i++) {
    let letter = first[i];

    // {a:3, n:1, g:1, r:1 , m:1}
    lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
  }
  // {a:3, n:1, g:1, r:1 , m:1}
  console.log(lookup);

  for(let i = 0 ; i < second.length ; i++){
    let letter = second[i];

    // 만일 값을 빼려는 프로퍼티가 0을 가지고 있다면 false이므로(0은 javascript에서 false로 판별) false가 return 된다.
    if(!lookup[letter]){
      return false;
    } else {
      lookup[letter] -= 1;
    }
  }

  // {a:0, n:0, g:0, r:0 , m:0}
  console.log(lookup);

  return true;
}

II. 다중 포인터 패턴

다중 포인터 패턴은 배열 또는 리스트와 같은 순차적인 데이터 구조에서 여러 개의 포인터를 사용하여 특정한 조건을 만족하는 원소를 탐색하거나 처리하는 알고리즘 설계 패턴입니다. 이 패턴은 선형 탐색 알고리즘을 최적화하거나 특정한 조건을 만족하는 원소를 찾는 데 유용하게 사용될 수 있습니다.

일반적으로 다음과 같은 절차를 따릅니다.

  1. 초기화: 포인터 변수를 초기 위치로 설정합니다. 일반적으로 첫 번째 원소를 가리키도록 설정합니다.
  2. 반복: 포인터를 이동시키고 조건을 확인하여 원하는 조건을 만족하는지 확인합니다. 조건을 만족하지 않으면 다음 원소로 포인터를 이동시킵니다. 조건을 만족하는 원소를 찾으면 해당 원소에 대한 처리를 수행합니다.
  3. 탐색 종료: 데이터 구조의 끝에 도달하거나 원하는 결과를 얻을 때까지 반복합니다.

다음과 같이 숫자가 담긴 배열에서 다른 숫자에 더하면 가장 먼저 0이 되는 쌍을 찾는 문제를 봅시다.

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

이 문제에 대한 단순 해결법을 봅시다.

js
function sumZero(arr){
  for(let i = 0 ; i < arr.length ; i++){
    for(let j = i + 1 ; j < arr.length ; j++){
      if(arr[i] + arr[j] === 0){
        return [arr[i], arr[j]];
      }
    }
  }
}

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

이중 for문을 사용하며 n의 영향을 받습니다. 시간복잡도 수치로 표기하면 O(n²)와 같습니다. 똑같이 시간,공간 복잡도가 O(n)수치가 나오도록 수정해봅시다.

js
function sumZero(arr){
  let left = 0;
  let right = arr.length - 1;
  while(left < right){
    // 배열내 양쪽 숫자를 더한다.
    let sum = arr[left] + arr[right];
    if(sum === 0){
      // 양쪽 수의 합이 0이라면 각 쌍을 반환한다.
      return [arr[left], arr[right]];
    } else if(sum > 0){
      // 만일 쌍의 합이 0보다 큰 경우 right를 감소한다.
      right--;
    } else{
      // 만일 쌍의 합이 0보다 작은 경우 left를 감소한다.
      left++;
    }
  }
}

// 배열내 숫자는 작은순으로 정렬되어있는것을 기억해야한다.
// [-4, 10] X , [-4, 3] X, [-3, 3] O 
sumZero([-4,-3,-2,-1,0,1,2,3,10]) 
sumZero([-4,-3,-2,-1,0,5,10]) // undefined

이 코드에는 두 개의 포인터가 사용됐습니다. 양쪽에서 가운데로 이동하는 방식입니다.

추가로 작은순으로 정렬된 배열을 인자로 주면 해당 배열의 고유한 값의 개수를 반환하도록 해봅시다. 진행방향은 양 포인터 둘다 왼쪽에서 시작합니다.

js
countUniqueValue([1,1,1,1,1,2]) // 2
countUniqueValue([1,2,3,4,4,4,7,7,12,12,13]) // 2
countUniqueValue([]) // 0
countUniqueValue([-2,-1,-1,0,1]) // 4

첫 번째 인덱스, 두 번째 인덱스를 비교하여 값이 다른 경우 얼마나 값이 다른지 진행하면서 갯수를 구할 수 있습니다.
또는 배열 자체를 사용하여 고유 값을 저장하는 실용적인 응용 또한 가능합니다. 처음 위치부터 고유한 값을 만드는 방식이죠.
첫 번째 인덱스는 고정시키면서 두 번째 인덱스를 이동해가며 값이 다른 경우 첫 번째 인덱스 다음 위치의 값으로 변경하고 첫 번째 인덱스를 우측으로 다시 이동하는 방식으로 풀이하면 됩니다.
두 번째 인덱스가 끝에 다다르면 첫 번째 인덱스 까지의 숫자만 남기면 되는거죠. 이 경우 시간복잡도는 O(n)입니다.

다음과 같이 풀이할 수 있습니다.

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