[알고리즘] Frequency Counter Pattern

 

강의를 들으면서 먼저 강의시작전에 풀어보는 문제로 

 

 

아래의 예시와 같이 순서와 상관없이 해당 문자가 포함되어 있으면 true

하지만 여기서 빈도수는 첫번째 문자열과 동일해야함

 

validAnagram('', '')  --> true
validAnagram('cat', 'atc') --> true
validAnagram('love', 'lovve') --> false

 

그래서 저는 우선 받아온 문자를 배열로 만들고 두 배열의 길이가 다르다면 제일 먼저 return false를 해주고, for문으로 구하기로 생각했습니다. 

 

// validAnagram('', '') true
// validAnagram('cat', 'atc') true
// validAnagram('love', 'lovve') false

function validAnagram (str1, str2) {

    var str1Arr = str1.split('');
    var str2Arr = str2.split('');

    // 만약에 str1 & str2의 길이가 다르다면 return false
    if (str1Arr.length !== str2Arr.length) {
        return false;
    }

    // 길이가 같은데 str1의 i의 값이 str2에 포함되어 있고 
    for (var i=0; i<str1Arr.length; i++) {
        if (str2Arr.includes(str1Arr[i])){
            // str2Arr에 해당 값을 splice
            var str2Ind = str2Arr.indexOf(str1Arr[i]);  // 해당 알파벳의 index 값을 리턴
            str2Arr.splice(str2Ind, 1); // 받아온 index 자리를 잘라내기
        }else{
            return false;
        }
    }
    return true;
}

validAnagram('love', 'lovve');

 

첫번째 기준의 배열의 i 번째의 값이 두번째 배열에 includes 하고 있으면, str2Arr에 indexOf로 인덱스 값을 받아옵니다. 그리고 받아온 index값을 사용해서 str2Arr에 splice로 해당 위치의 값을 제거합니다. 

그리고 해당 값이 includes 했을때 찾지 못했다면 return false를 합니다.

 

 

 

강의에서 이러한 예시에 사용하기 좋은 방법으로는 빈도카운터패턴을 사용하라고 합니다. 

 

• 기준을 삼을수 있는 빈도카운터 객체를 생성하여 사용할 것
• 중첩루프는 사용하지말 것 
• O(n)의 시간복잡도를 만들 것

 

// 빈도카운터패턴
function validAnagram (str1, str2) {

    if (str1.length !== str2.length) {
        return false;
    }

    // 빈도카운터 객체 생성 
    const lookup = {};

    // 객체 데이터 셋팅해주기
    for (let i=0; i<str1.length; i++) {
        // i번째 알파벳 담아오기
        let letter = str1[i];
        // ex. a 가 lookup 객체에 이미 있다면 +1 없다면 1로 셋팅해주기
        lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
    }

    for (let i=0; i<str2.lenth; i++) {
        let letter = str2[i];
        if (!lookup[letter]){
            return false;
        } else {
        	// lookup에서 -1 해주기 
            lookup[letter] -= 1;
        }
    }
    return true;
}

validAnagram('love', 'loves');

 

빈도카운터패턴 코드도 맨 우선적으로는 두 문자열의 길이가 다르다면 바로 return false를 해주었습니다. 

그리고 바로 lookup이라는 객체를 생성해주었고, 이 객체는 기준으로 삼아줄 배열의 키와 값들을 저장 시켜주는 역할을 합니다.

 

그리고 for문이 돌면서 만들어놓은 객체에 첫번째 문자열들의 알파벳을 가져옵니다. 그리고 lookup에 해당 알파벳이 있다면 1을 더해주고, 해당 알파벳이 없다면 1로 셋팅해줍니다.  

즉, 예로 들자면 { l : 1, o : 1, v : 2 .....} 이런식으로 for문이 돌면서 키와 값을 저장해줍니다.

 

이렇게 기준을 삼을 수 있는 객체에 데이터를 저장해주었으면 두번째 문자열에 for문을 돌면서 str2의 i번째 알파벳이 lookup객체에 있다면 1씩 감소를 시켜줍니다. 그리고 해당 알파벳이 lookup객체에 없다면 return false가 됩니다. 

 

이렇게 객체를 만들어서 사용하면 코드는 조금은 길어보이지만!

 

시간복잡도는 3n으로 O(n)이 되어집니다.