[leetcode 2024/02/05] 49. Group Anagrams

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

LeetCode - The World's Leading Online Programming Learning Platform

 

1. 접근 방법 

이번 문제는 시간초과로 꽤 애를 먹었다.

 

처음에 접근한 방법으로는 Counter 방법이었다. 

Counter를 이용하여, 알파벳을 key로, 해당 알파벳의 개수를 value로 한 후,

이를 비교해서 같다면, 같은 list에 넣어주는 방식으로 진행하였다.

 

하지만, 문자열 하나하나 당 Counter를 이용하는 방법은 시간 초과가 나기에 쉬웠다.

 

따라서 다음으로 접근한 방법이, sorted 였다.

들어온 문자열에 대해서 sorted를 해주게 된다면, 같은 anagram 문자열들은 같은 sorted 된 값을 가지게 될 것이기 때문이다.

 

따라서 sorted된 것을 key로 가지고, value들을 넣기 시작한다면, 실행 시간을 대폴 줄일 수 있다.

 

또한 코드에서, defaultdict(list) -> 를 사용하였는데, 이에 대해서 잘못 알고 있었기에

다시 한번 짚고 넘어갈 생각이다.

또한 Counter도 명확히 알지 못했기에 이에 대해서도 이야기 해보려고 한다.

 

1) 시간 초과가 난 코드

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        list=[]
        while strs:
            sub_list=[]
            remove_list=[]
            sub_list.append(strs.pop())
            for i in strs:
                if Counter(sub_list[0])==Counter(i):
                    sub_list.append(i)
                    remove_list.append(i)
            for k in remove_list:
                strs.remove(k)
            list.append(sub_list)
        return list

 

시간 초과가 난 코드는 Counter를 이용해서 같은 anagrams 인지 확인하고자 하였다.

 

Counter은  파이썬의 collections 모듈에 있는 특별한 자료형이다.

Counter은 주로 문자열이다. 리스트와 같은 반복 가능한 데이터에서 요소의 등장 횟수를 세는 데 사용된다.

즉, 리스트 내의 각 요소가 몇 번씩 나타나는지, 또는 주어진 문자열에서 각 문자가 몇 번 나타나는지 등을 쉽게 찾아낼 수 있다.

from collections import Counter

# 문자열에서 문자의 등장 횟수를 세기
counter_example = Counter('hello world')
print(counter_example)  # 결과: Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, ' ': 1, 'w': 1, 'r': 1, 'd': 1})

 

이런식으로 결과가 나오게 된다. 

 

2) defaultdict가 무엇인지 알아보자.

 

2. 코드

from typing import List
from collections import Counter, defaultdict


class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ordered = defaultdict(list)  # 기본값이 list인 딕셔너리 생성
        for s in strs:
            ordered[''.join(sorted(s))].append(s)

        return list(ordered.values())

solution=Solution()
strs = ["eat","tea","tan","ate","nat","bat"]

result = solution.groupAnagrams(strs)

print(result)

 

defaultdict는 말 그대로 dictionary의 일종이다. 즉, dictionary의 subclass이다.

이는 딕셔너리를 생성할 때 기본 값을 설정하는 기능을 추가한 것이다.

즉, 존재하지 않는 키에 대해 첫 조회 시, 미리 정의된 초기값을 반환한다.

 

따라서 키가 딕셔너리에 없는 경우에 대한 예외를 처리하는 코드를 작성할 필요가 없어 코드를 간결하게 만들 수 있다.

 

즉, 존재하지 않는 키에 대해 값을 추가하려고 하면, 리스트가 자동으로 생성된다. 

만약 일반 딕셔너리를 사용했다면, 해당 키가 딕셔너리에 존재하는지를 먼저 확인하는 추가적인 코드가 필요하다.

 

즉, 

[1] defaultdict(list) 를 통해서, 키가 딕셔너리에 없는 경우에 대한 예외를 처리한 경우

 

from collections import defaultdict

# 리스트를 기본값으로 하는 defaultdict 생성
dd_list = defaultdict(list)

# 존재하지 않는 키에 대해 값을 추가하려고 하면, 리스트가 자동으로 생성됩니다.
dd_list['dogs'].append('Rufus')
dd_list['dogs'].append('Kathrin')

 

[2] 일반 딕셔너리를 이용해서, 키가 딕셔너리에 없는 경우에 대한 예외를 코드로서 처리해주어야 하는 경우 

pets = {}

# 'dogs' 키에 대해 값을 추가하기 전에 키가 존재하는지 확인
if 'dogs' not in pets:
    pets['dogs'] = []  # 존재하지 않으면 빈 리스트를 할당
pets['dogs'].append('Rufus')

 

이런식으로 in 을 이용해서, 추가하고자 하는 키가 dogs에 있는지를 확인해주어야 한다.

 

다음으로, 문제를 풀이한 코드의 경우, sorted를 이용해서, string에 대해서 정렬해주었다.

정렬을 하게 되었을 때, 다른 문자열과 동일하다면, 같은 anagrams를 가지고 있는 것으로 판단할 수 있다.

따라서 sorted를 이용해주었다.

즉, bac 를 정렬한 것은 abc

cba를 정렬한 것은 abc

같은 정렬된 값을 가짐을 확인할 수 있다.

 

2. 코드

from typing import List
from collections import Counter, defaultdict


class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ordered = defaultdict(list)  # 기본값이 list인 딕셔너리 생성
        for s in strs:
            ordered[''.join(sorted(s))].append(s)

        return list(ordered.values())

solution=Solution()
strs = ["eat","tea","tan","ate","nat","bat"]

result = solution.groupAnagrams(strs)

print(result)