[Javascript] 백준 6996: 애너그램

문제

두 단어 A와 B가 주어졌을 때, A에 속하는 알파벳의 순서를 바꾸어서 B를 만들 수 있다면, A와 B를 애너그램이라고 한다.

두 단어가 애너그램인지 아닌지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수(<100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 길이가 100을 넘지 않는 단어가 공백으로 구분되어서 주어진다. 단어는 알파벳 소문자로만 이루어져 있다.

출력

각 테스트 케이스마다 애너그램인지 아닌지를 예체 출력과 같은 형식으로 출력한다. 

출력 형식

정확한 출력 형식은 제출에서 언어를 Java로 설정하면 확인할 수 있다.

예제 입력 1 복사

3
blather reblath
maryland landam
bizarre brazier

예제 출력 1 복사

blather & reblath are anagrams.
maryland & landam are NOT anagrams.
bizarre & brazier are anagrams.

---

문제 풀이

 이중 루프나 sort를 이용하면 쉽게 풀리는 문제입니다. 그러나 이중 루프 O(N^2)나 sort O(NlogN)보다 빠른 O(N)의 시간복잡도를 가지도록 구현하기위해 객체를 이용한 카운팅 방식을 선택했습니다.

const [N, ...input] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

// 두 단어를 받아 애너그램인지 확인하는 함수
function validAnagram(word1, word2) {
  // 두 단어의 길이가 다르면 false 반환
  if (word1.length !== word2.length) {
    return false;
  }

  // 첫번째 단어를 쪼개서 문자별 개수 카운팅하는 객체 생성
  const word1Counter = {};

  for (let el of word1) {
    word1Counter[el] = (word1Counter[el] | 0) + 1;
  }

  for (let el of word2) {
    // 2번째 단어의 알파벳이 word1Counter에 없으면 false
    if (!word1Counter[el]) {
      return false;
      // 있으면 -1
    } else {
      word1Counter[el] -= 1;
    }
  }

  //위 테스트를 모두 거쳐서 통과되었으면 true 반환
  return true;
}

input.map((words) => {
  const [word1, word2] = words.split(" ");
  if (validAnagram(word1, word2)) {
    console.log(`${word1} & ${word2} are anagrams.`);
  } else {
    console.log(`${word1} & ${word2} are Not anagrams.`);
  }
});