49. Group Anagrams

• 주어진 단어들 사이에서 출현빈도수가 같은것들만 묶어서 출력
• 출력할때 순서는 길이와 사전순이다.
  
  Input: strs = ["eat","tea","tan","ate","nat","bat"] Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
  -> eat, tea, ate는 알파벳 횟수가 동일하므로 같은 군에 속한다. 
  -> output에는 길이와 사전순 정렬이 필요하다.
  
  
  
• 1차 아이디어
  collection을 이용해서 빈도수를 세고, collection.Counter끼리 비교
  -> 시간 초과

    result = []
    for str in strs:
        if not result:
            result.append([str])
        else:
            flag = False
            for items in result:
                if collections.Counter(items[0]) == collections.Counter(str):
                    items.append(str)
                    flag = True
                    break
            if not flag:
                result.append([str])


    for item in result:
        item.sort(key=lambda x:x)
    result.sort(key=lambda x:len(x))
    return result

 

• 2차 아이디어
  단어별 아스키 코드값의 총합을 구해서 집합을 만든다. 
  -> 아스키 코드 총합이 같은것끼리 묶이는 현상 발생 (["duh","ill"])

    result = dict()
    for str in strs:
        cur = 0
        for item in str:
            cur += ord(item)
        if cur in result.keys():
            result[cur].append(str)
        else:
            result[cur] = [str]
    result = [item for item in result.values()]
    for item in result:
        item.sort(key=lambda x:x)
    result.sort(key=lambda x:len(x))
    return result

 

• 3차 아이디어
  시간 초과가 나는 이유를 자세히 보면 배열이 여러개 들어오고, 그 배열을 for문으로 두번 돌리기때문이다 
  이를 해결하기 위해서는 다른 아이디어가 필요하다.
  
  Anagram을 처음으로 돌아가보자. 
  각 문자열에 같은 문자가 몇번 나왔는지만 비교하면된다. 
  -> 비교 횟수를 구하지말고, 차라리 문자열 자체를 정렬하자. 
  -> "ate", "tea", "eat"를 사전순으로 정렬하면 모두 "aet"가 된다. 
  -> 이것을 key로 하고, 값을 구하면 된다.

# default dict사용...초기값을 지정해줄 필요가 없어 편하다. 
result = collections.defaultdict(list)

for s in strs:
	#문자열을 정렬하면, list가 나오는데 join함수를 이용해서 문자열로 만들자.
    result[''.join(sorted(s))].append(s)

 

• 다른 사람 풀이중 신기했던 것
  내가 생각한 아스키 코드 이용하는 것인데, 중요한것은 dict의 키 값에 tuple 자체가 들어갈 수 있다는 것이었다 
  이 방법을 생각했다면 2번째 풀이로도 풀수 있겠다는 생각이 들었다.

    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        ans[tuple(count)].append(s)

    return ans.values()