[python/leetcode] 49번 group anagrams 문제 풀이

https://leetcode.com/problems/group-anagrams

Group Anagrams - LeetCode

 

 

요약 : 같은 요소로 구성된 문자열을 그룹 짓기

 

로직은 다음과 같다.

1. 같은 애너그램 형식이라면 문자열을 내림차순으로 정렬했을 때 동일하다

2. 딕셔너리에 정렬된 문자열을 키 값으로, 각각의 문자열을 밸류에 담는다.

3. 밸류만 리턴한다.

 

def groupAnagrams(strs) :
    dic = {}
    for s in strs:
        # 내림차순을 key로 설정
        key = ''.join(sorted(s))
        if key in dic:
            dic[key].append(s)
        else:
            dic[key] = [s]

    # print(dic)
    # {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}

    # 밸류만 모아서 리턴
    return list(dic.values())

strs = ["eat","tea","tan","ate","nat","bat"]
print(groupAnagrams(strs))
# [["bat"],["nat","tan"],["ate","eat","tea"]]

 

 

개선한다면…

 

딕셔너리를 dic = {} 로 초기화하는 대신

collections.defaultdict(list) 을 사용하면

dic에 키값이 있는지 없는지 분기할 필요가 없다.

 

defaultdict 은 key가 없을 경우 에러가 나지 않고 기본 값으로 정했던 것을 밸류로 해서 찾은 키를 생성해준다.

위의 예시에서 list를 기본값으로 넣었는데

defaultdict(list)

이는 카:밸류 에서 밸류의 기본값으로 빈배열이 들어간다는 뜻이다

 

따라서 if 조건으로 key가 있는지 확인하지 않고

없는 키값에 바로 추가하면

에러가 발생하지 않고, 기본값인 빈 배열에 s가 추가된다.

def groupAnagrams(strs) :
    dic = collections.defaultdict(list)

    for s in strs:
        # 내림차순을 key로 설정
        key = ''.join(sorted(s))
        dic[key].append(s)

    # 밸류만 모아서 리턴
    return list(dic.values())