[해쉬]아나그램

문제

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

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

 

문제풀이

key와 Value를 한 쌍으로 적재하는 Map() 객체를 사용하여 각 문자열에 대해 자료구조를 만든다.두 문자열에서 Key의 값인 알파벳이 다르다면 아나그램의 전제 조건을 성립하지 못하기 때문에 그대로 연산을 종료한다.만약 중첩 for문 내에서 동일한 Key값을 찾은 뒤 그 값이 동일할 경우 아나그램 조건을 성립하고 마지막까지 순회했을 때도찾지 못한다면 이 또한 전제 조건을 성립하지 못하기 때문에 그대로 연산을 종료한다.

 

코드

function solution(str1, str2) {
  let answer = 0;
  let sH1 = new Map();
  let sH2 = new Map();

  for (let x of str1) {
    if (!sH1.has(x)) {
      sH1.set(x, 1);
    } else {
      sH1.set(x, sH1.get(x) + 1);
    }
  }
  for (let x of str2) {
    if (!sH2.has(x)) {
      sH2.set(x, 1);
    } else {
      sH2.set(x, sH2.get(x) + 1);
    }
  }
  for (let [key1, val1] of sH1) {
    if(answer === false) break;
    for (let [key2, val2] of sH2) {
      if (key1 !== key2) continue;
      //두 개의 키값이 다를 경우 이하 연산을 생략하고 다음 인덱스를 참조
      if (val1 === val2) answer = true;
      else answer = false;
    }
  }
  return answer;
}

let str1 = "AbaAeCe";
let str2 = "baeeACA";
console.log(solution(str1, str2));

 

문제풀이2

위와 같이 각 문자열마다 Map 객체를 생성해주고 해당 Map 객체에 Key와 Value 값을 주기 위해 동일한 수행을 하는 반복문을수행케 하는 것은 비효율적이다.

 

이를 대신에 하나의 문자열에 대해서만 Map 객체를 생성해주고 해당 Map 객체에 적재되어 있는 데이터 값과 또 다른 문자열에대한 데이터 값을 비교하는 식으로 대체하고자 한다.

 

포함되어 있는 문자의 갯수가 같다는 말은 문자열을 순회하며 Map 객체와 동일한 문자가 있을 시, 해당 문자의 횟수를 1씩 상쇄시켜 준다면 결국 마지막엔 0이 된다는 것이다. 즉, 0 이상이면 문자열의 갯수가 n개 만큼 더 있다는 의미이고 0 이하일 경우 n개 만큼 덜 있다는 의미로 생각할 수 있다.

 

코드

function solution(str1, str2) {
  let answer;
  let sH1 = new Map();

  for (let x of str1) {
    if (!sH1.has(x)) {
      sH1.set(x, 1);
    } else {
      sH1.set(x, sH1.get(x) + 1);
    }
  }

  for(let x of str2) {
    if(!sH1.has(x)) {
      answer = false
      break;
    }
    sH1.set(x, sH1.get(x) - 1);
    if(sH1.get(x) === 0) answer = true;
    else if(sH1.get(x) < 0) {
      answer = false;
      break;
    }
  }
  return answer;
}

let str1 = "AbaAeCe";
let str2 = "baeeACA";
console.log(solution(str1, str2));

---

function solution(str1, str2){
                let answer="true"; 
                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 "false";
                    sH.set(x, sH.get(x)-1);
                }
                return answer;
            }
            
            let a="AbaAeCe";
            let b="baeeACA";
            console.log(solution(a, b));