알고리즘 (2) : 문제해결패턴 1) Frequency Counter

일반적인 문제 해결 패턴들에 대해 살펴보려고 한다.

같은 문제가 나온다는 보장은 없지만 다양한 곳에 적용이 가능하다.

 

 

1) Frequency Counter.

 

공식적인 이름은 없다고 한다. 이전에 MDN array.reduce 사용 예제에서 발견한 패턴으로 코딩테스트를 풀 때 종종 쓰던 방법이다.

객체를 사용해서 값과 빈도를 수집하는 것. 중첩 순회를 피할 수 있게 해서 좀 더 나은 효율을 만들어 낼 수 있다.

두개 세개 네개의 개별 루프가 중첩된 하나의 루프보다 낫다는 것.

 

 

ex) 

2개의 배열을 허용하는 same이라는 함수를 작성하십시오. 배열의 모든 값이 두 번째 배열에 해당하는 값을 가지면 참을 반환해야 합니다.

따라서 첫 번째 배열에는 여러 값이 있는데 두 번째 배열의 값이 정확히 동일하지만 제곱되어 있는지 알고자 합니다.

하지만 순서는 상관 없으니 동일할 필요는 없고 그저 제곱만 하면 됩니다. 섞일 수 있지만 값의 빈도는 동일해야 합니다.

 

=> 1, 2, 3이 있고 4, 1, 9가 있으면 참이 반환되어야 합니다.

 

- 일반풀이 - indexOf 로 인해 중첩순회가 일어나고 O(n^2)

function solution(arr1, arr2){
    if(arr1.length !== arr2.length){
        return false;
    }
    for(let i = 0; i < arr1.length; i++){
        let correctIndex = arr2.indexOf(arr1[i] ** 2)
        if(correctIndex === -1) {
            return false;
        }
        console.log(arr2);
        arr2.splice(correctIndex,1)
    }
    return true;
}

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

 

- use Frequency Counter

 

function solution(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        
    }

    for(let key in frequencyCounter1){
        if(!(key ** 2 in frequencyCounter2)){
            return false
        }
        if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
            return false
        }
    }
    return true
}

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

 

 

- Frequncy Counter Refactoring.

 

const solution = (arr1, arr2) => {

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

const FrequencyCounter = {}

for (let ele of arr2) {
	FrequencyCounter[ele] = FrequencyCounter[ele] ? FrequencyCounter + 1 : 1
    }


for (let ele of arr1) {

if (!FrequencyCounter[ele ** 2]) false;

 else {
	FrequencyCounter[ele] -= 1 
	}
}
return true;

}

 

 

 

 

 

+ 다음과 같은 질문을 해보는게 좋다.

경계 조건이 무엇인지, 여백은 어떻게 할지, 공백, 마침표, 구두점, 숫자를 고려하는지, 대소문자.

 

여러 데이터가 있어 서로 비교하는 경우, 데이터가 같은 개별데이터 조각(개별 데이터 제곱..)으로 구성되어 있는지, 숫자가 같은 숫자로만 구성되는지, 순서는 다른지 등 다양한 패턴에 적용할 수 있다.