TIL 29, 코드카타: 같은 알파벳으로 이루어진 단어

공유오피스로 출근하는 시간 전체를 잡아먹었던, 꽤나 고민했던 코드카타. 기억에 남아, 남겨본다

---

문제

다음과 같이 input이 주어졌을 때,같은 알파벳으로 이루어진 단어끼리 묶어주세요.

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]
output에서 순서는 상관없습니다.

---

나의 풀이

1. 최종 결과를 저장할 배열을 생성. (최종 배열)
2. 같은 알파벳으로 이루어진 단어들의 묶음을 저장할 배열을 만든다. (단어 묶음 배열)
3. 항상 첫번째 단어를 기준으로 잡는다. 우선 첫번째 단어를 단어 묶음 배열에 저장. 이 후 단어 배열에서 첫번째 문자를 지워준다.
4. 이후 단어 배열을 순회하면서, 기준 단어와 같은 알파벳으로 이루어진 단어를 찾는다. 찾았다면 해당 문자를 단어 묶음 배열에 저장.
5. 저장후, 해당 문자를 단어 배열에서 지워준다.
6. 순회가 끝나면, 단어 묶음 배열을 최종 배열에 저장.
7. 루프를 돌면서 3~6번을 반복한다. 최종적으로 단어 배열의 길이가 0이 되면 종료.
8. 최종 배열을 리턴한다.

코드로 풀면 아래와 같다.

// checker 함수는 인자로 주어진 두 개의 스트링이 같은 알파벳으로 이루어졌는지 확인한다. 
const checker = (str1, str2) => {
  let isIdentical = true;
  const src = str1.length >= str2.length ? str1 : str2;
  const target = str1.length < str2.length ? str1 : str2;
  for (let i = 0; i < src.length; i++) {
    if (!target.includes(src[i])) {
      isIdentical = false;
      break;
    }
  }
  return isIdentical;
}

// 본 함수
const groupAnagrams = strs => {
  const result = [];
  while (strs.length !== 0) {
    const sameWords = [];
    const firstWord = strs[0];
    sameWords.push(firstWord)
    strs.splice(0,1);
    for (let i = 0; i< strs.length; i++) {
      if (checker(firstWord, strs[i])) {
        sameWords.push(strs[i]);
        strs.splice(i,1);
        i -= 1;
      }
    }
    result.push(sameWords)
  }
  return result
};

---

나의 풀이 문제점

1. 루프를 너무 많이 사용.

---

모범 답안

내가 생각했던 것 보다 훨씬 깔끔한 풀이가 가능하다. 모범 답안의 접근은 아래와 같다.

1. 최종 결과물이 담길 객체를 생성.
2. 단어 배열을 한번만 순회하고, 각 단어를 이용하여, 키 값을 만든다.
3. 키는 단어의 문자를 알파벳 순으로 정렬시킨 것. 따라서, 같은 알파벳으로 이루어진 단어의 경우 같은 키 값을 가진다.
4. 결과 객체에 키가 없으면 값으로 빈 배열을 생성.
5. 키에 해당하는 배열에 단어를 푸시.
6. 순회가 끝나면, 각 키에는 같은 알파벳으로 이루어진 단어들의 배열이 담긴다. 따라서, 키 값만 모아주면 완성.

const groupAnagrams = strs => {
    const map = {};
    
    for (let str of strs) {
        const key = [...str].sort().join('');

        if (!map[key]) {
            map[key] = [];
        }

        map[key].push(str);
    }
    
    return Object.values(map);
};

---

와우. 해쉬 맵과 비슷한 느낌으로 풀면 좋을 것 같다라는 생각은 했지만, 정확하게 어떻게 로직을 짜야할 지 몰랐었다. 그래서 때려 맞추기 식으로 했었는데, 모범 답안을 보니, 생각보다 간단했었네.. 분발합시다.