(MEDIUM) LeetCode No.49 - Group Anagrams 풀러가기

문제

• 문자열 배열을 받아 애너그램 단위로 그룹핑하기

애너그램이란 ?
문자를 ㅈ배열하여 다른 뜻을 가진 단어로 바꾸는 것을 말한다.
이 문제에서는 간단하게 단어 내 글자 조합이 같은 것이라고 생각하자.
ex) tea, ate, eat은 모두 a, t, e 로 조합이 되어있다.

문제풀이

일단 문제를 푸는데 실패했다. 아래 제출 코드를 2시간 7분을 소요해서 작성하였고, 교재에 있는 정답을 확인하고 공부하였다.

내가 제출한 코드 (실패)

• Language: Python3

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        total_list = []
        dic = {}

        for word in strs:
            length = len(word)

            temp_list = []
            for i in range(length):
                temp = word[i:i+1][0]
                temp_list.append(temp)
                temp_list.sort()

            dic[word] = temp_list

        for key, value in dic.items():
            return_list = []
            temp_value = value

            for key, value in dic.items():
                if (temp_value == value) & (key not in return_list):
                    return_list.append(key)
                    return_list.sort()

            if return_list not in total_list:
                total_list.append(return_list)

        return total_list

• 위와 같이 작성하면 주어진 예제는 정확하게 처리가 되고 Accepted가 뜬다.
• 하지만 제출하기를 누르면 다른 input에 의해 걸리게 된다.

아주 간단한 코드로 풀수가 있다

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
    	# defaultdict은 존재하지 않는 키에 접근 했을때, 기본값이 할당되어 있기 때문에 에러가(keyerror) 나지 않음
        # 딕셔너리는 K, V를 함께 할당해야하는데 defaultdict은 key만 할당될 시에 value를 default로 할당하여 에러가 나지 않는다.
        # 괄호 안의 list는 해당 딕셔너리의 value가 list임을 표현
        anagrams = collections.defaultdict(list)

        for word in strs:
            anagrams["".join(sorted(word))].append(word)

        return list(anagrams.values())
    

• 2시간이 넘게 고생했는데, 이렇게 너무나도 쉽게 풀릴 거라고 예상도 못했다.
• 문자열에 그냥 sorted 하면 처리가 되다니...
• defaultdict 에 대해서 배울 수 있었다.
• 문자열 배열에서 join을 이용해서 합칠 수 있다는 것을 배울 수 있었다.

join의 활용

# 문자 배열에서의 활용
input = ['orange', 'apple', 'banana']
print("".join(sorted(input)))

# 숫자 배열에서의 활용
input2 = [9, 1, 2, 3, 4, 5]
print("".join(map(str, input2)))
#-> 912345

# 정렬 후 처리한다면
print("".join(map(str, sorted(input2))))
#-> 123459

결과

내가 직접 풀었다면 얼마나 좋았을까... 하지만 이렇게 모르는 것을 배워가면 되니까 화이팅하자.