문제 해결 기법

1. frequency counter

uses objects or sests to collect values/frequencies of values
빈도수를 측정하는 객체를 만든다.

Problem : 두 개의 배열을 받아서 첫 번째 배열의 모든 값들의 제곱값이 두번째 배열에 존재할때 true를 반환하는 함수(same)를 만드시오.

ex)

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

그냥 풀었을 때

function same(arr1, arr2){
  if(arr1.length !== arr2.length)
    return false;

  for(let val of arr1){

    let index = arr2.indexOf(val**2);
    // indexOf -> 반복문을 돈다. -> O(n^2)

    if(index === -1)
      return false;
      // 해당 키가 존재하지 않는다

    arr2.splice(index, 1)
    // 빈도수가 같아야하기 때문에 일치하는 키는 없앤다.           
  }

  return true;    
}

시간 복잡도는 O(n^2)

frequency counter 기법을 이용했을 때

function same(arr1, arr2){

  let arr1Count = {};
  let arr2Count = {};

  if(arr1.length !== arr2.length)
    return false;

  for(let val of arr1){
    arr1Count[val] = (arr1Count[val] || 0) + 1;
  }
  // arr1 값이 없다면 1로 설정, 없다면 이미 있는 값에 +1

  for(let val of arr2){
    arr2Count[val] = (arr2Count[val] || 0) + 1;
  }
  // 위와 동일 

  for(let val in arr1Count){

    if(!arr2Count[val**2])
      return false;
    // 상응하는 키가 있는지 검사

    if(arr1Count[val] !== arr2Count[val**2])
      return false;
    // 상응하는 키가 있다면 빈도수가 같은지 검사

  }        

  return true;
}

시간 복잡도는 O(n^2)

해설 : arr1과 arr2의 각 값들의 빈도를 저장하는 객체 arr1Count, arr2Count를 만들고 이 두개의 객체를 비교

2. multiple pointers

여러개의 index를 상황에 맞게 조절해(처음, 중간, 끝) 문제를 효율적으로 해결하는 기법

Problem : 오름차순으로 정렬된 정수들의 배열을 받아 더해서 0이 되는 짝의 배열을 반환하는 함수(sumZero)를 만드시오. (없다면 undefined 반환)

ex)

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

그냥 풀었을 때

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]];
    }
  }
}

시간 복잡도 => O(n^2)

multiple pointers 적용

function sumZero(arr){

  let left = 0;
  let right = arr.length -1;
  // 두 개의 Index 설정

  while(left<right){

    let sum = arr[left] + arr[right];

    if(sum === 0){
      return [arr[left], arr[right]];
    } else if(sum<0){
      left++;
    } else{
      right--;
    }

  }
}

시간 복잡도 => O(n)

해설 : 양 끝에 index 존재(left, right). 양 끝의 숫자들을 더해 0보다 크다는 것은 right(끝 index)에 해당하는 값(양수)이 더 크다는 것을 의미하기 때문에 right 값을 하나 줄인다.(해당 배열은 오름차순 정렬이다!!) 마찬가지로 양 끝의 숫자들을 더해 0보다 작다는 것은 left(처음 index)에 해당하는 값(음수)이 더 크다는 것을 의미하기 때문에 left 값을 하나 늘린다. 더해서 0이면 그 짝을 반환.

3.sliding window

하나의 window를 만들어 상황이 따라 값이 증가하거나 감소
window는 array나 number
배열, 문자열에서 subset을 찾을때 유용

Problem : 정수들의 배열과 숫자 n을 받아 배열 안에서 n개의 연속 요소들의 최대합을 반환하는 함수(maxSubarraySum)을 만드시오.

ex)

maxSubarraySum([1,2,5,2,8,1,5], 2) --> 10
maxSubarraySum([4,2,1,6], 1) --> 6

그냥 풀었을 때

function maxSubarraySum(arr, num){

  if(arr.length<num)
    return null;

  let maxSum = -Infinity;
  let tempSum;

  for(let i=0; i<arr.length-num+1; i++){

    tempSum = 0;

    for(let j=0; j<num; j++){
      tempSum += arr[i+j];
    }

    if(tempSum > maxSum){
      maxSum = tempSum;
    }

  }

  return maxSum;
}

시간 복잡도는 --> O(n^2)

sliding window 기법 적용 후

function maxSubarraySum(arr, num){

  if(arr.length<num)
    return null;

  let maxSum = 0;
  let tempSum = 0;

  for(let i=0; i<num; i++){
    tempSum += arr[i];
  }

  maxSum = tempSum;

  // window --> maxSum

  for(let i=0; i<arr.length-num+1; i++){

    tempSum = tempSum - arr[i] + arr[i+num];
    // 젤 앞의 값은 빼고 젤 뒤의 값을 더한다

    if(tempSum>maxSum)
      maxSum = tempSum;
  }    

  return maxSum;
}

function maxSubarraySum(arr, num){

  let maxSum = 0;
  let tempSum = 0;

  if (arr.length < num) return null;

  for (let i = 0; i < num; i++) {
    tempSum += arr[i];
  }

  maxSum = tempSum;

  // window --> maxSum 

  for (let i = num; i < arr.length; i++) {

    tempSum = tempSum - arr[i - num] + arr[i];
    // 위와 동일

    maxSum = Math.max(maxSum, tempSum);

  }

  return maxSum;
}

두가지 버전 다 시간 복잡도 => O(n)

해설 : 처음에 0부터 n-1까지의 합을 구한다.(=window). 앞의 값을 빼고 뒤의 값을 추가하면서 그 전 값과 비교한다.