효율성 - 7. 아나그램(Hash Map)

문제

Anagram이란 두 문자열이 알파벳의 나열 순서는 다르지만
그 구성이 일치하면 두 단어는 아나그램이라고 한다.

예를 들어 AbaAeCe 와 baeeACA 는 알파벳 나열 순서는 다르지만
그 구성은 A(2) a(1) b(1) C(1) e(2) 로 알파벳과 그 개수가 모두 일치한다.
즉, 위 두 문자열은 아나그램이다.

그렇다면 아나그램을 판별하는 프로그램을 작성하시오.

입력예제 1
AbaAeCe
baeeAcA

출력예제 1
YES

입력예제 2
abaCC
Caaab

출력예제 2
NO

 

 

풀이

2022.02.23 - [CS/Algorithm] - 효율성(해쉬) - 6. 학급 회장

 Map을 만들고 key값에 해당하는 value값을 Counting해주는 방법이 위의 문제 풀이 방법과 유사하다.

 

먼저 처음 입력되는 abaCC 문자열(str1)을 Map 객체에 넣어준다.

a b a C C -> Map 객체로 저장

그리고 두 번째 문자열(str2)인 C a a a b를 반복문으로 탐색한다.

조건 (1. str2의 요소가 sH에 없다면, 2. sH[key] 값이 0이면)

에 맞지 않으면 NO를 return 하고

위 조건과 상관없다면 sH[key] 값을 1씩 감소하면서 value값을 상쇄시켜나간다.

 

 

코드

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

  for (let x of str1) {
    if (sH.has(x)) sH.set(x, sH.get(x) + 1);
    else sH.set(x, 1);
  }
  console.log(sH);
  
  for (let x of str2) {
    if (!sH.has(x) || sH.get(x) === 0) return "NO";
    sH.set(x, sH.get(x) - 1);
  }
  return answer;
}
// let a="AbaAeCe";
// let b="baeeACA";
// console.log(solution(a, b)); //YES

// let a="AABBCC";
// let b="EEFFGG";
// console.log(solution(a, b)); //NO

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

 

출처

자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의