[효율성/해쉬] 아나그램

문제

 

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

길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세 요. 아나그램 판별시 대소문자가 구분됩니다.

▣ 입력설명
첫 줄에 첫 번째 단어가 입력되고, 두 번째 줄에 두 번째 단어가 입력됩니다. 단어의 길이는 100을 넘지 않습니다.

▣ 출력설명
두 단어가 아나그램이면 “YES"를 출력하고, 아니면 ”NO"를 출력합니다.

▣ 입력예제 1 AbaAeCe baeeACA

▣ 출력예제 1 YES

▣ 입력예제 2 abaCC
Caaab

▣ 출력예제 2 NO

---

결과

X

내가 푼 방식-

const solution = (str1, str2) => {
  let sH1 = new Map();
  
  for(let x of str1){
    if(sH1.has(x)) sH1.set(x, sH1.get(x)+1);
    else sH1.set(x, 1);
	}
  
  for(let x of str2) {
    
  }

  console.log('sH1', sH1)
}

solution('AbaAeCe','baeeACA')

접근과정

1. map자료구조를 사용했으나 접근하지 못함. 

 

모범답안

  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);
      }
      for(let x of str2){
          if(!sH.has(x) || sH.get(x)==0) return "NO";
          sH.set(x, sH.get(x)-1);
      }
      return answer;
  }

리뷰

1. 문제 자체는 간단한 문제이나, 해쉬 함수의 개념과 사용법에 익숙치 않았다. 해쉬함수에 대해 조금 더 찾아봐야겠다.

2. 머리 속으로만 정리 하려다보니 잘되지 않는 것 같다.  아이패드를 사용해서 그래프를 그려가며 접근법을 먼저 파훼후 코드를 짜는 연습이 필요하다.

3. 아나그램 여부는 결국 첫번째 인자로 만든 해쉬의 키값이 있는 지 여부와 그 밸류값이 같은지 여부로 판단하는 것이다. 

4. 그렇기에 그 hash의 키 값이 없다면 혹은 그 키값의 밸류값이 다르다면 바로 NO로 리턴할 수 있다. 

5. 만약 위에 해당사항이 없다면 해쉬 키값의 밸류를 하나씩 상쇄시킨다.