Group Anagrams

코테에서 매번 망하고 진짜 진짜 이제는 코테를 열심히 할 때가 되었다 싶어서 새로운 마음으로 백준 말고 새로운 사이트를 찾아서 시작함. 이젠 정말 물러날 곳도 없음

내 답안

class Solution {
    /**
     * @param {string[]} strs
     * @return {string[][]}
     */
    groupAnagrams(strs) {
       // 비교할 때 sort해서 비교
       let strsCopy=strs.slice().map((el)=>el.split('').sort().join(''));
       let strsSet=new Set(strsCopy);
       let strsSetArray=Array.from(strsSet);
       let answer=Array.from({length:strsSetArray.length}, ()=>[]);
       for (let i=0;i<strs.length;i++){
        let strSort=strs[i].split('').sort().join('');
        if (strsSetArray.includes(strSort)){
            answer[strsSetArray.indexOf(strSort)].push(strs[i]);
        }
       }
           return answer;

    }
}

단점

• 미개하다. 저 수많은 변수를 보소.
• 자바스크립트는 sort가 느리다. NlogN임. 자바스크립트는 대체;; 앱/웹 프론트/백 모두 다 할 수 있는 장점을 가진 굉장한 언어지만 속도가 왜 저럴까(싱글스레드, 인터프리터, 표준 라이브러리 부족(진짜 화남. 우선순위큐도 없음. 파이썬은 이분탐색도 bisect로 한다는데))

다른 풀이1. 해시테이블

class Solution {
    /**
     * @param {string[]} strs
     * @return {string[][]}
     */
    groupAnagrams(strs) {
        const res = {};
        for (let s of strs) {
            const count = new Array(26).fill(0);
            for (let c of s) {
                count[c.charCodeAt(0) - 'a'.charCodeAt(0)] += 1;
            }
            const key = count.join(',');
            if (!res[key]) {
                res[key] = [];
            }
            res[key].push(s);
        }
        return Object.values(res);
    }
}

흐름
1. 각 문자열을 순회하면서 알파벳 개수를 기록한(애너그램이기 때문) count배열을 만든다.
2. count.join('') 또는 count.join(',')를 고유한 key로 삼는다.
3. 같은 애너그램 문자열은 같은 key를 가지게 된다.
4. key를 기준으로 res 객체에 문자열을 push한다.

장점

성능 최적화에 아주 좋다. 시간복잡도가 O(n)다.

단점

내 머리로 생각하기 어렵다.

근데 굳이 객체로 안하고 Map을 써도 될 것 같다. 아래와 같이 쓰면 되는 것.

class Solution {
    /**
     * @param {string[]} strs
     * @return {string[][]}
     */
    groupAnagrams(strs) {
      const res=new Map();
      for (let s of strs){
        const count=new Array(26).fill(0);
       	for (let c of s){
         count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++; 
        }
        const key=count.join(','); // ,로 안해도 되고 그냥 붙여도 됨
        
        // 만약 해당 키값을 가진게 res에 없다면
        if (!res.has(key)){
         res.set(key, []); 
        }
        res.get(key).push(s);
      }
      return Array.from(res.values());
    }
}

여기서 확인하고 가는 객체와 Map의 차이점

	객체{}	Map
key 타입	문자열/심볼만 가능	모든 타입 가능(ex.배열)
key 순서 보장	보장X(ES6이후는 거의 됨)	입력 순서 보장됨
내장 메서드	적음(Object.keys 등)	풍부함(get, set, has, forEach, entreis 등)
성능	작은 규모에서는 비슷	큰 데이터셋에서는 Map이 우세

객체 메소드

메소드 이름	설명
Object.keys(obj)	key리스트(문자열 배열) 반환
Object.values(obj)	value 리스트 반환
Object.entries(obj)	[key, value]쌍의 배열 반환
Object.hasOwnProperty()	객체에 해당 key가 직접 존재하는지 확인
Object.assign(target, source)	객체 복사
Object.freeze(obj)	객체를 수정 불가로 만듦
Object.fromEntries()	entries 배열 --> 객체로 변환

const obj = { a: 1, b: 2 };
console.log(Object.keys(obj)); // ['a', 'b']
console.log(Object.entries(obj)); // [['a', 1], ['b', 2]]

Map 메소드

메소드 이름	설명
set(key, value)	키-값 추가
get(key)	키에 해당하는 값 반환
has(key)	키 존재 여부 반환(true/false)
delete(key)	키 삭제
clear()	전체 삭제
keys()	모든 key 반복자 반환
values()	모든 value 반복자 반환
entries()	[key, value] 반복자 반환
forEach(callback)	모든 요소에 콜백 적용

const map = new Map();

map.set('name', 'Alice');
map.set(42, 'age');
console.log(map.get('name')); // 'Alice'
console.log(map.has(42));     // true
console.log([...map.keys()]); // ['name', 42]

다른 풀이2. 정렬

class Solution {
    /**
     * @param {string[]} strs
     * @return {string[][]}
     */
    groupAnagrams(strs) {
        const res = {};
        for (let s of strs) {
            const sortedS = s.split('').sort().join('');
            if (!res[sortedS]) {
                res[sortedS] = [];
            }
            res[sortedS].push(s);
        }
        return Object.values(res);
    }
}

나랑 비슷하긴 한데 로직이 훨씬 간결하다.

장점

• 객체를 사용해서 간단하다.