📖 문제 해결 패턴(Problem Solving Patterns)

다음은 알고리즘 문제를 패턴화해 문제 해결에 도움을 줄 수 있는 패턴들이다.

• Frequency Counter
• Multiple Pointers
• Sliding Window
• Divide and Conquer
• Dynamic Programming
• Greedy Algorithms
• Backtracking
• ...

이 중 오늘 포스팅에서는 Frequency Counter, 빈도 수 세기라고 강의에서 칭하는 패턴에 대해 이야기하겠다.

📌 빈도 수 세기 : Frequency Counter

이 패턴을 '빈도 수 세기'로 명명한 이유는, 이 패턴의 기본적인 개념이 자바스크립트의 객체 또는 set를 사용해 값과 빈도를 수집하는 것에 주목하기 때문이다.

데이터들이 서로 비슷한 값으로 구성되어 있는지, 서로 애너그램인지. 하나의 값이 다른 값에 포함되어 있는지, 데이터를 입력값이나 두 개 이상의 빈도 혹은 특정하게 발생하는 빈도와 비교할 때 유용하다.

예시를 한 번 살펴보자.

2개의 배열을 받는 함수 same이 있다. 이 함수는 만약 첫번째 배열의 모든 값의 제곱이 두번째 배열의 값들과 일치하면 true를 반환한다. 이때 값들은 섞일 수 있지만(인덱스는 상관없음을 의미), 값의 빈도수는 동일해야 한다.

same([1,2,3],[4,1,9]); //true
same([1,2,3],[1,9]); //false
same([1,2,1],[4,1,4]); //false(빈도가 같아야 한다.)

📌 Naive Solution

빈도 수 세기 패턴을 사용하지 않은 naive한 방법은 다음과 같다.

//naive한 방법( O(N^2))

function same(arr1, arr2){
    //두 배열의 길이 다르면 무조건 false
    if(arr.length !== arr.length){
        return false;
    }
    //첫번째 배열의 제곱의 값을 두번째 배열에서 찾아 index를 구함
    //indexOf()는 값이 없으면 -1를 리턴하므로 false
    //
    for(let i=0; i<arr1.length; i++){
        let correctIndex = arr2.indexOf(arr1[i] **2);
        if(correctIndex === -1){
            return false;
        }
        //첫번째 배열의 제곱의 값과 일치하는 값이 두번째 배열에서 있으면 제거
        arr2.splice(correctIndex,1);
    }
    return true;
}

for의 내부에 indexOf()와 splice()가 있어 시간 복잡도는 O(n^2)이 된다.

📌 Refactored Solution

위의 솔루션을 리팩토링해 시간 복잡도를 O(n)으로 하는 풀이는 다음과 같다.

//O(n))
function same(arr1, arr2){
    //두 배열의 길이 다르면 무조건 false
    if(arr1.length !== arr2.length){
        return false;
    }

	//빈도 수를 세기 위한 객체 frequencyCounter1, frequencyCounter2
    let frequencyCounter1 = {};
    let frequencyCounter2 = {};

	//arr1의 값들을 순회하면서 val1에 할당한다
    //frequencyCounter1에 이미 val1를 키로하는 값이 존재하면 원래의 값에 +1해주고, 아니라면 0으로 초기화해준뒤 +1해준다.
    for(let val1 of arr1){
        frequencyCounter1[val1] = (frequencyCounter1[val1] || 0)+1;
    }
	//위와 동일
    for(let val1 of arr2){
        frequencyCounter2[val1] = (frequencyCounter2[val1] || 0)+1;
    }

	//frequencyCounter1의 키를 순회하면서 key에 할당한다.
    for(let key in frequencyCounter1){
    	//만약 key의 제곱이 frequencyCounter2에 없으면 false 반환
        //존재 여부를 따지는것임
        if(!(key ** 2 in frequencyCounter2)){
            return false;
        }
        //만약 frequencyCounter2에서 frequencyCounter1의 키 값을 제곱으로 하는 값을 키로 갖는 값이 frequencyCounter1에서 key의 값과 갖지 않으면 false 반환
        //빈도 수 따짐
        if(frequencyCounter2[key**2] !== frequencyCounter1[key]){
            return false;
        }

        return true;
        
    }
    
    
}

📌 Anagrams Solution

빈도 수 세기 패턴을 이용해서 애나그램 문제를 해결해보자!

두 문자열이 주어진다. 두번째 문자열이 첫번째 문자열의 애나그램인지를 판별하는 함수를 작성하자. 애나그램은 문자가 그 안에 있는 경우뿐만 아니라, 안에 있는 문자들이 나타나는 횟수, 빈도가 정확한지를 확인해야 한다.

validAnagram("",""); //true
validAnagram("aaz","zza"); //false
validAnagram("anagram","nagaram"); //true
validAnagram("rat","car"); //false
validAnagram("awesome","awesom"); //false
validAnagram("qwerty","qeywrt"); //true
validAnagram("texttwisttime","timewisttext"); //true

앞에서 배운 빈도 수 세기 패턴을 이용해 다음과 같이 해결했다.

function validAnagram(str1,str2){
	 //두 배열의 길이 다르면 무조건 false
    if(str1.length !== str2.length){
        return false;
    }
	//빈도 수를 세기 위한 객체 charCounter1, charCounter2
    const charCounter1 = {};
    const charCounter2 = {};

	//유사 배열 객체인 str1의 값들을 순회하면서 val에 할당한다
    //charCounter1 이미 val를 키로하는 값이 존재하면 원래의 값에 +1해주고, 아니라면 0으로 초기화해준뒤 +1해준다.
    for(let val of str1){
        charCounter1[val] = (charCounter1[val] || 0)+1;
    }
	//위와 동일하다
    for(let val of str2){
        charCounter2[val] = (charCounter2[val] || 0)+1;
    }

	//charCounter1 키를 순회하면서 key에 할당한다.
    for(let key in charCounter1){
    //만약 charCounter1에서 key를 키로 갖는 값이 charCounter2에서의 key로 갖는 값과 다르면 false를 반환한다.
        if(charCounter1[key] !== charCounter2[key]){
            return false;
        }
    }
    //그게 아니라면 true를 반환한다.
    return true;

}

강의에서의 풀이

function validAnagram(str1,str2){
    //길이 비교해서 다르면 false
    if(str1.length !== str2.length){
        return false;
    }

    const lookup = {};

    //객체 lookup에 만약 해당 키를 갖는 값이 이미 있었으면 +1 없으면 1로 초기화
    for(let i=0; i<str1.length; i++){
        let letter = str1[i];

        lookup[letter] ? lookup[letter]+=1 : lookup[letter] = 1;
    }


    //str2의 각 문자를 lookup에 있나 비교
    //없으면 false
    //있으면 -1처리해줌(계속 소거해서 만약 없으면 false를 리턴해주기 위햐)
    for(let i=0; i<str2.length; i++){
        let letter = str2[i];

        if(!lookup[letter]){
            return false;
        }else{
            lookup[letter] -=1;
        }
    }
    return true;

}

✏️ Frequency Counter - sameFrequency

문제를 풀어보자

sameFrequency라는 함수를 작성해라. 자연수가 주어지고, 이 두 자연수의 각 자리들이 같은 빈도 수를 갖는지 판별할 수 있도록 하자.
시간 복잡도는 O(n)이어야 한다.

sameFrequency(182,281) // true
sameFrequency(34,14) // false
sameFrequency(3589578, 5879385) // true
sameFrequency(22,222) // false

function sameFrequency(num1, num2){
	//num1, num2를 문자열로 바꿔 str1, str2에 할당한다.
    const str1 = num1.toString();
    const str2 = num2.toString();
    
    //빈도를 세기 위한 numberCount객체
    const numberCount = {};
    
    //일단 길이가 다르면 빈도가 같을 수 없으므로 길이가 다르면 false반환
    if(str1.length !== str2.length){
        return false;
    }
		
     //str1의 각 자리를 letter에 할당하고,
 	 //객체 numberCount에 만약 해당 letter를 키로 갖는 값이 이미 있었으면 +1 없으면 1로 초기화
    for(let i=0; i<str1.length; i++){
        let letter = str1[i];

        numberCount[letter] ? numberCount[letter]+=1 : numberCount[letter] = 1;
    }
    
    //str2의 각 자리를 letter에 할당한다.
    for(let i=0; i<str2.length; i++){
        let letter = str2[i];
    	//numberCount객체에 letter를 키로 갖는 값이 없으면 false반환
        if(!numberCount[letter]){
            return false;
        //있다면 numberCount객체에서 letter를 키로 갖는 값에 -1해준다.
        }else{
            numberCount[letter] -=1;
        }
    }
    return true;
    
}

✏️ Frequency Counter - areThereDuplicates

areThereDuplicates라는 함수를 작성해라. 이때 인수의 개수는 정해지지 않는다. 받은 인수들 중에 중복된 값이 있는지 판별해라.
시간,공간 복잡도는 O(n)이어야 한다.

areThereDuplicates(1, 2, 3) // false
areThereDuplicates(1, 2, 2) // true
areThereDuplicates('a', 'b', 'c', 'a') // true

//spread구문을 사용해 인수를 동적으로 받을 수 있도록 한다.
function areThereDuplicates(...arr) {
	//중복 값을 찾기위한 객체 duplicateCount
    const duplicateCount = {};
    
    //arr의 값을 순회해 val에 할당
    for(let val of arr){
    	//duplicateCount 이미 val를 키로하는 값이 존재하면 원래의 값에 +1해주고, 아니라면 0으로 초기화해준뒤 +1해준다.
        duplicateCount[val] = (duplicateCount[val] || 0) +1;
        
        //만약 duplicateCount에서 val를 키로하는 값이 1보다 크면 중복된 값이 있다는 말이므로 true를 리턴해주면 된다.
        if(duplicateCount[val] >1){
            return true;
        }
    }
    return false;
}

💗 Frequency Counter Solution

다음은 위의 두 문제에 대한 강의에서의 솔루션이다.

sameFrequency Solution

function sameFrequency(num1, num2){
  let strNum1 = num1.toString();
  let strNum2 = num2.toString();
  if(strNum1.length !== strNum2.length) return false;
  
  let countNum1 = {};
  let countNum2 = {};
  
  for(let i = 0; i < strNum1.length; i++){
    countNum1[strNum1[i]] = (countNum1[strNum1[i]] || 0) + 1
  }
  
  for(let j = 0; j < strNum1.length; j++){
    countNum2[strNum2[j]] = (countNum2[strNum2[j]] || 0) + 1
  }
  
  for(let key in countNum1){
    if(countNum1[key] !== countNum2[key]) return false;
  }
 
  return true;
}

나는 객체를 하나로 사용해 비교하는 방법을 찾았는데(소거해가면서) 해설에서는 초반 풀이와 같이 객체 두개를 이용하는 방법을 선택했다.

areThereDuplicates Solution

function areThereDuplicates() {
  let collection = {}
  for(let val in arguments){
    collection[arguments[val]] = (collection[arguments[val]] || 0) + 1
  }
  for(let key in collection){
    if(collection[key] > 1) return true
  }
  return false;
}

나처럼 ...전개 구문을 사용해서 인자를 받는게 아니라 arguments 객체를 사용했다.
collection객체에 arguments의 각 값을 키로 하는 값이 존재하는지 비교 후, 있으면 기존 값에 +1, 없으면 0으로 초기화 후 +1해준다.

collection을 순회하면서 각 키를 key에 할당하고, collection객체에서 key를 키로 갖는 값이 1보다 크면 true를 반환한다.

📘 참고 자료
https://www.udemy.com/course/best-javascript-data-structures/