5. 문제 해결 패턴

김민재·2023년 2월 21일
0

알고리즘

목록 보기
8/9

1. 문제 해결 패턴 소개

2. 빈도 수 세기 패턴 (Frequency Counter)

  • 자바스크립트 객체 사용해 다양한 값과 빈도를 수집할 쓰이는 패턴
  • 여러 데이터와 입력값이 서로 비슷한 값으로 구성되어 있는지 값이 다른 값에 포함되는지 여부를 비교할 때 등

예시 - 2개의 배열을 허용하는 same 함수 작성, 배열의 모든 값이 두 번째 배열에 해당하는 값을 가지면 true 반환

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

단순 접근법

function same(arr1, arr2){
  // 두개의 배열을 받는데 2번째 배열이 첫 번째 인자의 값에 제곱 값이 되면 true 반환
  let answer = false
  if(arr1.length !== arr2.length) return answer
  for(let i=0; i<arr2.length; i++){
    if(arr1.some(el => el*el===arr2[i])) answer = true
    else answer = false
    // 다른 풀이
    /*
    let correctIndex = arr2.indexOf(arr[i]**2)
    if(correctIndex === -1){
    	return false
    }
    arr2.splice(correctIndex,1)
    */
  }
  return answer
}

same([1,2,3] , [4,1,9])
// true
same([1,2,3] , [1,9])
// fale
same([1,2,1] , [4,1,1])
// false
  • 이러한 접근법은 O(N^2), 제곱시간이 사용되어 순진한 접근법으로 가능한 않는게 좋다

빈도 카운터 패턴 접근법

  • loop를 두개로 나눠 중첩된 개별 루프가 아닌 선형시간인 O(N)으로 수정되도록 하기
function sameForFrequency(arr1, arr2){
  // 두개의 배열을 받는데 2번째 배열이 첫 번째 인자의 값에 제곱 값이 되면 true 반환
  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){
    console.log(key)
         if(!(key ** 2 in frequencyCounter2)){
           // key 제곱이 frequencyCounter2의 키 값인지 확인
           return false
         }
     // if(frequencyCounter2[key ** 2]!==frequencyCounter1[key]){
     //       return false
     //     }
   } 

  
  return true
}
sameForFrequency([1,2,3,2,5],[9,1,4,4,25])
profile
자기 신뢰의 힘을 믿고 실천하는 개발자가 되고자합니다.

0개의 댓글