[해시] 아나그램

자바스크립트 알고리즘 문제풀이 강의를 듣고 정리한 내용입니다.

 

 

 

 

📋 문제

아나그램이란 두 문자열이 알파벳의 나열 순서는 다르지만 구성이 일치한 것을 말한다.

예를 들면 AbaAeCe와 baeeACA는 알파벳의 나열 순서는 다르지만 알파벳의 구성은 다음과 같다.

• AbaAeCe => A(2) a(1) b(1) C(1) e(2)
• baeeACA => A(2) a(1) b(1) C(1) e(2)

두 문자열의 알파벳과 그 알파벳의 개수가 모두 일치하므로 둘 중 한 문자열을 재배치하면 나머지 하나의 문자열을 만들 수 있다.

 

길이가 같은 두 개의 문자열이 주어지면 두 문자열이 아나그램인지 판별하여 그 결과를 출력한다.

이때 두 문자열의 대소문자는 구분된다.

 

 

👉 입력

첫 번째 줄에 첫 번째 문자열이 입력된다.

두 번째 줄에 두 번째 문자열이 입력된다.

이때 두 문자열은 모두 길이가 100을 넘지 않는다.

 

 

👈 출력

두 문자열이 아나그램이면 "YES", 아니면 "NO"를 출력한다.

 

 

📝 풀이

 

function makeMap(str, map) {
    map = new Map();

    for (const i of str) {
        if (map.has(i)) map.set(i, map.get(i) + 1);
        else map.set(i, 1);
    }

    return map
}

function solution(str1, str2) {
    let answer = "YES";
    let map1, map2;

    map1 = makeMap(str1, map1);
    map2 = makeMap(str2, map2);

    for (const [k, v] of map1) {
        if (!map2.has(k) || map2.get(k) !== v) answer = "NO"
    }

    return answer;
}

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

 

입력으로 주어진 문자열 a, b를 순회하며 key - value 쌍을 저장할 map1, map2를 선언한다.

이후 makeMap()에서 문자열의 알파벳과 등장 횟수를 저장한다.

 

a, b의 알파벳과 등장 횟수를 저장하는 작업이 끝났다면 map1의 key - value를 순회하며 map2를 확인한다.

이때 map2에 해당 key가 없거나 map2에 해당 key가 있어도 value값이 동일하지 않으면 a와 b는 아나그램이 될 수 없기 때문에 answer에 "NO"를 저장한다.

만약 for문을 돌며 if문에 걸리지 않았다면 a와 b는 아나그램이고 answer는 초기값 그대로 "YES"가 된다.

 

위 과정을 조금 다르게 생각하면 아래와 같은 풀이가 가능하다.

 

function solution(str1, str2) {
    let answer = "YES";
    let map = new Map();

    for (const i of str1) {
        if (map.has(i)) map.set(i, map.get(i) + 1);
        else map.set(i, 1);
    }

    for (const i of str2) {
        if (!map.has(i) || map.get(i) === 0) return "NO"
        map.set(i, map.get(i) - 1);
    }

    return answer;
}

let a = "AbaAeCe";
let b = "baeeACA";
console.log(solution(a, b));

 

주어진 문자열 a와 b 중 a만 순회하며 알파벳과 그 등장 횟수를 key - value 쌍으로 map에 저장한다.

첫 번째 for문이 끝나면 map에는 a의 구성 요소가 담기게 된다.

 

두 번째 for문에서는 문자열 b의 각 알파벳을 순회한다.

각 알파벳을 순회할 때 현재 알파벳이 map에 key로 존재하고 value가 0이 아니라면 해당 key의 value값을 1씩 뺀다.

만약 key가 map에 존재하지 않거나 해당 key가 있음에도 value가 0이라면 알파벳의 등장 횟수가 다르다는 뜻이므로 a와 b는 아나그램이 될 수 없기 때문에 즉시 "NO"를 리턴하며 작업을 끝낸다.

if문에 걸리지 않는다면 a와 b는 아나그램이라는 뜻이며 answer는 초기값 "YES"가 그대로 리턴된다.