문제 해결 패턴

문제 1.

배열 2개가 주어지고 첫번째 배열에서 제곱한 값이 두번째 배열안에 있는 수와 같으면 True

다르면 False를 반환해라

내 풀이

/* O(n^2) => for문안에 indexOf
 문제: 배열 2개가 주어지고 첫번째 배열에서 제곱한 값이 두번째 배열안에 있는 수와 같으면 True
 다르면 False를 반환해라

 방법은 많지만 그중 O(n)의 시간 복잡도를 가질수 있게 풀어보는게 목적 -> 빈도수 세기 패턴(?)
 */

function squareArr(arr1,arr2){
  if (arr1.length!==arr2.length){
    console.log('false : different length')
    return false
  }
  for (let i = 0; i < arr1.length; i++) {
    let checkIndex=arr2.indexOf(arr1[i]**2)
    if (checkIndex===-1){
      console.log('false : result is -1')
      return false
    }
    // checkIndex 1 , 0 , 2
    console.log(arr2);
    arr2.splice(checkIndex,1) // 1, 0, 2 순서대로 1개씩 제거
  }
  console.log('empty arr');
  return true;
}

squareArr([1,2,3],[4,1,9])

 

요구하는 풀이

function same(arr1, arr2){
    if(arr1.length !== arr2.length){
        return false;
    }
    let frequencyCounter1 = {}
    let frequencyCounter2 = {}
    for(let val of arr1){
        frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1
    }
    for(let val of arr2){
        frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1        
    }
    console.log(frequencyCounter1);
    console.log(frequencyCounter2);
    for(let key in frequencyCounter1){
        if(!(key ** 2 in frequencyCounter2)){
            return false
        }
        if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
            return false
        }
    }
    return true
}

same([1,2,3,2,5], [9,1,4,4,11])

문제 2

유효한 아나그램 : 두 개의 문자열이 주어지고 두 문자열이 철자 순서를 바꾼 말이면 True 아니면 False반환

빈도수 세기 패턴

ex) 'aaz' , 'zza' //false

    'anagram' , 'nagaram' '//true 이런식으로

풀이

function anagram(firstStr,secondStr){
    if(firstStr.length!== secondStr.length){
        return false;
    }
    const checkStr={};
#1.
    for (let i = 0; i < firstStr.length; i++) {
        let letter=firstStr[i];
        checkStr[letter] ?  checkStr[letter] +=1 : checkStr[letter]=1;   
    }
    console.log(checkStr);
#2.
    for (let i = 0; i < secondStr.length; i++) {
        let letter=secondStr[i]
        if(!checkStr[letter]){
            return false;
        }else{
            checkStr[letter]-=1;
        }
    }
    console.log("모두 0으로");
    return true;
}
anagram('anagram','nagaram')

 

설명

먼저 #1부분에 for문을 보게되면 letter변수에는 문자열이 하나씩 담길것이고 처음 받는 문자 -> anagram에서 a는 객체에 없으므로 삼항연산자에 false  즉, 1로 설정되게 된다. 그 뒤로로 없는 문자는 1로 설정되고 a가 다시 나왔을때 checkStr[letter]에서 true로 확인되므로 +1을 해주게된다.

console.log(checkStr) => { a: 3, n: 1, g: 1, r: 1, m: 1 }

#2부분에서는 만약 secondStr에 동일한 문자(key)가 존재한다면 1을 빼주는식으로해서 value가 모두 0이되면 true를 반환

하게 했다

 

다중 포인터

-Creating pointers or values that correspond to an index or position and move towards the beginning, end or middle based on a certain condition

Very efficient for solving problems with minimal space complexity as well

인덱스나 위치에 해당하는 포인터나 값을 만든 다음 특정 조건에 따라 중간 지점에서부터 시작 지점이나 끝 지점이나 양쪽지점을 향해 이동 시키는것

최소의 공간복잡성 문제를 해결하는데 매우 효과적이다

 

문제 3

정렬된 배열이 주어졌을때 합이 0이 되는 첫 짝을 찾아야한다. 이 값이 있으면 return 시키고 없으면 undefined를 리턴해라

시간복잡도 O(n^2)

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){
        console.log([arr[i],arr[j]]);
        return [arr[i],arr[j]]
      }
    }
  }
}

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

O(n)

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

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

문제 3-1

countUniqueValues

배열에 숫자는 정렬되서 주어지고 음수가있을 수도 있다

EX) [1,1,1,2] => 2 ( 1이랑 2) [1,4,4,12,13] 4 (1 ,4 12 ,13)

 

내 풀이 ( 테스트 통과 )

function countUniqueValue(arr){
  let countNum=0;
  let indexCount=0;
  let count=0;
  while(indexCount<=arr.length){
    countNum=arr[indexCount]
    indexCount++;
    if(arr[indexCount]===countNum){
      continue;
    }else{
      count++;
    }
  }
  console.log(count);
}

countUniqueValue([-2,-1,-1,0,1])

슬라이딩 윈도우(Sliding Window)

This pattern involves creating a window which can either be an array or number from one position to anther

Depending on a certain condition, the window either increases or closes (and a new window is created)

Very useful for keeping track of a subset of data in an array/string etc.

이 패턴은 한 위치에서 다른위치로 배열 또는 숫자가 될 수 있는 window를 만드는 것을 포함한다

특정 조건에 따라 window는 증가하거나 닫힌다(새로운 window가 생성됨)

배열이나 문자열과 같은 일련의 데이터를 입력하거나 특정 방식으로 연속적인 해당 데이터의 하위 집합을 찾는 경우에 

유용하다

 

배열 뒤에 있는 n 값에 따라서 n만큼 배열 내부의 값을 더해서 가장 큰 값을 return해준다

양 옆에 있는 값만 가능하다 -> 1,2 / 2,5 가능 | 5,8 불가능 

EX) maxArrSum([1,2,5,2,8,1,5],2) -> 10

O(n)

function maxArrsum(arr,num){
  let maxSum=0;
  let tempSum=0;
  if(arr.length < num) return null;
  for (let i = 0; i < num; i++) {
    maxSum+=arr[i]
  }
  tempSum=maxSum;
  for (let i = num; i < array.length; i++) {
    tempSum=tempSum-arr[i-num]+arr[i]
    maxSum=Math.max(maxSum,tempSum)
  }
  return maxSum
}

우선 num 만큼의 숫자를 더해서 maxSum에 넣는다

임시로 tempSum에 보관해두고 for문을 통해서 array의 원소중 첫번째 인덱스에 있는 값을 빼고 비교해야할 값을 더해줘서 tempSum에 재할당한다. 그 후 Math.max를 통해 maxSum에 최대값을 넣어준다 

 

분할 정복(Divide and Conquer)

알고리즘을 공부해나가면서 엄청나게 많이 보게 될 것

 

문제 4

정렬된 배열이 주어지고 배열과 정수하나가 주어졌을때 배열안에 정수가 있으면 index를 return시키고 없으면 -1을 return

O(n)

function search(arr,n){
  for (let i = 0; i < arr.length; i++) {
    if(arr[i]===n){
      return i;
    }
    else{
      return -1;
    }
  }
}

search([1,2,3,4,5],4)

분할 정복

-> 중간지점부터 시작 

function search(arr,n){
  let min=0;
  let max=arr.length-1;
  while(min<=max){
    let middle=Math.floor((min+max)/2)
    let currentElement=arr[middle]

    if(arr[middle]<n){
      min=middle+1
    }
    else if (arr[middle]>n){
      max=middle-1
    }
    else{
      return middle
    }
  }
  return -1
}

search([1,2,3,4,5,6],4)