[알고리즘] 애너그램 걸러내기

Map과 Set을 공부하면서 모던 JavaScript 튜토리얼의 과제 중에 애너그램을 걸러내는 문제가 있었다. 

 

애너그램이란 단어나 문장을 구성하고 있는 문자의 순서를 바꾸어 다른 단어나 문장을 만드는 것이다. 다음은 한국어에서 음절 단위의 애너그램 예시이다. 

 

국왕 - 왕국

미개 - 개미

방배역 - 배방역

피노키오 - 키노피오

 

영어에서는 stressed - desserts, permission to dance - stories on pandemic 등이 애너그램이다. 

 

문제:
애너그램으로 만든 단어를 걸러내어 한 단어만 남기는 함수 aclean(arr)를 작성하세요.

// 예시
const arr = ["nap", "teachers", "cheaters", "PAN", "ear", "era", "hectares"];
aclean(arr) // [ 'PAN', 'hectares', 'era' ] 또는 [ 'nap', 'teachers', 'ear' ]

 

관건은 1) 애너그램이 같은 단어를 파악해서 2) 중복을 없앤 배열을 반환해야 한다. 

 

위의 사항을 조금 더 구체적으로 발전시켜 보면: 

 

1) 애너그램이 같은 단어를 파악하기 위해서 

- 원래 단어를 알파벳 순으로 정렬한다.

  가령 위의 예시에서 ear - are - era는 애너그램이 동일한 단어들이고, 이 단어들을 알파벳 순으로 정렬하면 모두 aer이다. 

 

2) 중복을 없앤 배열을 반환하려면 

- aer이 아닌 원래 단어 중 하나, 즉 ear, are, era 중의 하나를 배열의 요소로 반환해야 한다. 

- 알파벳 순으로 정렬한 aer과 원래의 단어(ear, are, era)는 연관성이 있는 자료이다. 

- 자료의 연관성을 표현할 때는 key-value 쌍을 저장할 수 있는 객체나 Map을 사용할 수 있다. 

- 하나의 객체 안에서 key는 고유하기 때문에 동일한 key에 대해 다른 value 값을 저장할 경우 마지막으로 저장한 key-value 쌍만이 객체에 남게 된다. (Map도 마찬가지이다.) 

 

이러한 생각의 전개를 바탕으로 코드를 작성해 보면 다음과 같다.

 

 

Map, Set을 배운 챕터에서 나온 문제이기 때문에 처음에는 중복을 없애려면 Set을 써야 한다고 생각했는데, 객체나 Map에서 key는 유일하기 때문에 for loop를 돌고 나왔을 때 obj에는 이미 중복이 제거된 데이터만 남아있게 된다. 

// for loop를 돌고 난 후 obj는 다음과 같다.
{ anp: 'PAN', aceehrst: 'hectares', aer: 'era' }

 

객체가 아닌 Map에 key-value 쌍으로 자료를 담을 수도 있지만, 애너그램 문제는 문자열 요소를 다루기 때문에 Map이 아닌 객체를 쓰는 편이 더 간단하다. 똑같은 방식으로 object 대신 Map을 쓴다면 코드는 다음과 같을 것이다. 

 

const aclean = (arr) => {
  const map = new Map();

  for (let word of arr) {
    const sorted = word.toLowerCase().split("").sort().join("");
    map.set(sorted, word);
  }

  return Array.from(map.values());
};

 

💡 배운 점 : 
간단한 문제였지만 객체나 Map이 자료의 연관성을 표현하는 자료구조라는 점과 그 안에서 key는 고유하다는 의미를 제대로 짚고 넘어갈 수 있는 문제였다.