아나그램
📌 아나그램이란, 하나의 단어나 구절의 문자들을 재배열하여 완전히 다른 단어나 구절을 만드는 것을 말한다. 이때 중요한 것은 원래 단어나 구절에 사용된 문자의 개수와 종류가 새로운 단어나 구절에서도 동일해야 한다는 점이다. 예를 들어, "listen"을 재배열해서 "silent"라는 단어를 만들 수 있다.
아나그램은 문자의 위치만 바꾸며, 추가적인 문자를 넣거나 기존 문자를 빼는 것은 허용되지 않기 때문에 퍼즐이나 언어 게임에서 자주 사용되며, 때로는 예술적이거나 재미있는 효과를 위해 사용되기도 한다고 한다. 😀
문제 설명
Anagram이란 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 합니다. 예를 들면 AbaAeCe 와 baeeACA 는 알파벳을 나열 순서는 다르지만 그 구성을 살펴보면 A(2), a(1), b(1), C(1), e(2)로 알파벳과 그 개수가 모두 일치합니다. 즉 어느 한 단어를 재 배열하면 상대편 단어가 될 수 있는 것을 아나그램이라 합니다. 길이가 같은 두 개의 단어가 주어지면 두 단어가 아나그램인지 판별하는 프로그램을 작성하세요.아나그램 판별시 대소문자가 구분됩니다.
▣ 입력설명
첫 줄에 첫 번째 단어가 입력되고, 두 번째 줄에 두 번째 단어가 입력됩니다.
단어의 길이는 100을 넘지 않습니다.
▣ 출력설명
두 단어가 아나그램이면 “YES"를 출력하고, 아니면 ”NO"를 출력합니다.
▣ 입출력 예
| input | output |
|---|---|
| AbaAeCe / baeeACA | YES |
| abaCC / Caaab | NO |
풀이
const anagram = (a, b) => {
let obj1 = {};
let obj2 = {};
for (let x of a) {
obj1[x] = obj1[x] ? obj1[x] + 1 : 1;
}
for (let x of b) {
obj2[x] = obj2[x] ? obj2[x] + 1 : 1;
}
console.log('obj1 :', obj1); // {A: 2, b: 1, a: 1, e: 2, C: 1}
console.log('obj2 :', obj2); // {b: 1, a: 1, e: 2, A: 2, C: 1}
if (Object.keys(obj1).length !== Object.keys(obj2).length) return 'NO';
let objKeys1 = Object.keys(obj1);
console.log('objKeys1 :', objKeys1); // ['A', 'b', 'a', 'e', 'C']
for (let x of objKeys1) {
if (obj1[x] === obj2[x]) {
return 'YES';
} else {
return 'NO';
}
}
};
let a = 'AbaAeCe';
let b = 'baeeACA';
console.log(anagram(a, b));👉 해시를 사용해서 풀어보자
"해시"는 각 문자를 키로 하고 해당 문자의 출현 횟수를 값으로 하는 객체(JavaScript에서는 일반적으로 객체를 해시맵으로 사용)를 사용하는 것을 말한다.
✍️ 아나그램은 철자 순서를 바꾼 말이다. 순서가 다르더라도 같은 철자를 동일하게 가지고 있는지 판별한다.
- 첫 번째 문자와 두 번째 문자 모두 어떤 문자가 몇 번 들어왔는지 객체(키와 값)로 저장한다.
-
두개의 객체가 서로 동일한 키와 값을 가지고 있는지 알 수 있나? 🧐
→ 먼저 각 객체의 키의 길이가 같은지 확인Object.keys한다. 키가 하나라도 더 많거나 적으면 false이다.
즉 모든 동일한 것 외에 추가로 다른 키와값이 들어올 수 없다.
⭐️ 객체에서는.length속성이 없기 때문에, 속성의 개수를 세어 길이를 알아내야 한다. 이는 Object.keys() 함수를 사용하여 객체의 키들을 배열로 변환한 후, 그 배열의.length속성을 사용하여 할 수 있다. -
hasOwnProperty() 를 통해서 각 키와 값을 비교한다. 특정 키에대한 값이 동일한지 서로 검사한다.
// MDN ex.) const object1 = {}; object1.property1 = 42; console.log(object1.hasOwnProperty('property1')); // Expected output: true console.log(object1.hasOwnProperty('toString')); // Expected output: false console.log(object1.hasOwnProperty('hasOwnProperty')); // Expected output: false
- 코드의 첫 번째 부분, 즉 문자의 출현 횟수를 계산하는 부분은 해시를 사용한 것.
여기서 문자(character)는 키(key)로, 그 문자의 출현 횟수는 값(value)으로 사용된다. 이는 해시맵의 전형적인 사용 사례라고한다.
obj1과 obj2 객체는 문자의 출현 횟수를 저장하기 위한 해시맵으로 사용된다.for (let x of a) { obj1[x] = obj1[x] ? obj1[x] + 1 : 1; } for (let x of b) { obj2[x] = obj2[x] ? obj2[x] + 1 : 1; } - 여기서는 계산된 해시맵을 사용하여 두 객체의 키-값 쌍을 비교한다. 이 과정에서 해시 함수를 새롭게 적용하거나 해시맵의 기본적인 특성을 이용하는 것은 아니라고 하는데.. 그러나 이 부분은 이미 생성된 해시맵(obj1과 obj2)을 이용해 두 문자열이 아나그램 관계인지를 판단한다. 😀
❗️하지만 여기서 문제가 있다. 모든 키가 일치할 때까지 반복하지 않고 서둘러 'YES'를 return한다는 것!for (let x of objKeys1) { if (obj1[x] === obj2[x]) { return 'YES'; } else { return 'NO'; } } // 수정된 코드 👇👇 for (let x of objKeys1) { if (obj1[x] !== obj2[x]) { return 'NO'; } } return 'YES'; ```
✍️ 해시와 해시맵에 대한 개념이 아직 좀 헷갈리고 실제로 내가 푼 방식이 그런 방식인 줄도 모르고 사용했지만😂 비슷한 문제를 계속 풀어나가면 감이 잡히겠지!
코드 개선하기
const anagram = (a, b) => {
if (a.length !== b.length) return 'NO'; // 1)
let frequencyCounter = {};
for (let char of a) { // 2)
frequencyCounter[char] = (frequencyCounter[char] || 0) + 1;
}
for (let char of b) { // 3)
if (!frequencyCounter[char]) return 'NO';
frequencyCounter[char] -= 1;
}
return 'YES';
};
let a = 'AbaAeCe';
let b = 'baeeACA';
console.log(anagram(a, b));-
1) 가장 처음에 두 문자 길이를 비교한다.
→ 굳이 각 문자열을 Obj로 만들고 Object.keys()를 굳이 사용하지 않아도 되며 빠른 리턴이 가능하다.🥲 -
2) frequencyCounter 객체에서 char라는 키를 확인한다. 만약 char 키가 이미 frequencyCounter 객체 안에 존재한다면, 그 키에 해당하는 값을 가져온다. 존재하지 않으면 0을 기본값으로 사용한다.
그런 다음 그 값에 1을 더하여frequencyCounter[char]에 다시 할당한다. 이때frequencyConter[char]가 처음으로 불려진다면undefined이므로 || 연산자에 의해 뒤의 0이 할당되는 것이다!😤 -
3) frequencyConter에 b의 char를
[]로 넣어서 값을 확인하는데, 이 과정에서 값(ex. 2)이 있다면 값은 truthy이므로 !truthy는 false가 된다. 즉 if문을 통과하여 기존 값(ex. 2)에서 1을 뺀다. 이렇게 모든 값을 하나씩 빼다가 해당값이 0이되고 거기서 또 1을 빼려고한다면, 빼기도 전에 0은 falsy한 값으로 취급되므로 !falsy 즉 true가 되어 return 'NO'를 반환한다.
✍️ solution
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;
}
let a = 'AbaAeCe';
let b = 'baeeACA';
console.log(solution(a, b));