[알고리즘] 아나그램 (해쉬)

문제

Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 합니다.
예를 들면 AbaAeCe 와 baeeACA 는 알파벳을 나열 순서는 다르지만 그 구성을 살펴보면 A(2), a(1), b(1), C(1), e(2)로 알파벳과 그 개수가 모두 일치합니다. 즉 어느 한 단어를 재배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 합니다.
길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세요.

아나그램 판별시 대소문자가 구분됩니다.

강사님의 풀이

function solution(str1, str2){
    let answer='YES'; 
    let hash = new Map();
    for(let x of str1){
        if(hash.has(x)) hash.set(x,hash.get(x)+1);
        else hash.set(x,1);
    }
    for(let x of str2){
        if(!hash.has(x) || hash.get(x)===0) return 'NO';
        //x 키값이 없거나, x의 value가 이미 0이면 아나그램이 아니므로 NO를 return
        else hash.set(x,hash.get(x)-1);
        //위 두 경우가 아니면 x의 value -1 값으로 set
    }

    return answer;
}

let a="abaaC";
let b="Caaab";
console.log(solution(a, b));

• 비교 대상 문자열을 map 객체화 하여, x를 키로 갯수를 set 한다.
• 문자열 2번을 반복문으로 돌며 map 객체에 key가 존재하는지, value가 0인지 판별해 아나그램 여부를 가린다.
• 문자열의 요소를 하나씩 소거하며 판별하는 방법

나의 풀이 1

function solution(str1, str2){
    let answer='YES'; 
    let hash = new Map();
    for(let x of str1){
        if(hash.has(x)) hash.set(x,hash.get(x)+1);
        else hash.set(x,1);
    }
    for(let x of str2){
        if([...hash.keys()].includes(x)) {
            hash.set(x,hash.get(x)-1);
        }
        else return 'NO';
    }
    for(let [key,val] of hash){
        if(val !== 0) return 'NO';
    }

    return answer;
}

let a="abaaC";
let b="Caaab";
console.log(solution(a, b));

• 풀이 설명을 듣고 작성했다. 강사님 풀이와 마찬가지로 x를 비교해 value를 하나씩 소거하는 방식.
• x가 map객체에 key로 존재하는지 확인하려고 [...hash.keys()].includes(x) 를 썼는데, 생각해보니 hash.has(x) 만 써도 여부를 확인할 수 있다.
• object.keys( ) 함수는 숫자키의 배열을 정렬된 순서로 반환한다.
• 일치되지 않는 조건을 확인해 앞에서 결과 return 해주는게 더 좋은 것 같다. for...of 문으로 map을 하나씩 돌며 val이 0이 아닐 경우를 찾아 return 'NO'를 하도록 반복되는 부분이 있다.

나의 풀이 2

function solution(str1, str2){
    let answer='YES'; 
    let h1 = new Map();
    let h2 = new Map();
    for(let x of str1){
        if(h1.has(x)) h1.set(x,h1.get(x)+1);
        else h1.set(x,1);
    }
    for(let x of str2){
        if(h2.has(x)) h2.set(x,h2.get(x)+1);
        else h2.set(x,1);
    }
    h1 = [...h1.entries()].sort().join('');
    h2 = [...h2.entries()].sort().join('');

    if(h1!==h2) return 'NO';

    return answer;
}

let a="abaCC";
let b="Caaab";
console.log(solution(a, b));

• 비교할 각 두 문자열을 map -> array 로 만든 뒤 join 해서 비교
• 지금보니 이럴거면 굳이 map 객체로 만들 필요가 없네...
• h1.entries( )로 key,value 값을 반환받고, 이를 spread 연산자로 넘겨 배열화함
• object.entries( ) 는 [key, value] 형식의 쌍으로 반환한다.
• 그리고 이를 정렬해서 join했는데 지금보니 굳이 이렇게 할 필요가 없군...

참고자료

[Map - JavaScript | MDN

 

Map - JavaScript | MDN

 

[Javascript] Map 객체 정렬하는 법