미소를뿌리는감자의 코딩
[leetcode 2024/02/05] 49. Group Anagrams 본문
https://leetcode.com/problems/group-anagrams/description/
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)
'코딩 테스트 > leetcode' 카테고리의 다른 글
[leetcode 2024/02/06] 232. Implementing Queue using Stacks (1) | 2024.02.06 |
---|---|
[leetcode 2024/02/06] 225. Implement Stack using Queues (0) | 2024.02.06 |
[leetcode 2024/02/06] 561. Array Partition (0) | 2024.02.06 |
[leetcode 2024/02/05] 15. 3Sum (0) | 2024.02.05 |
[leetcode 2024/02/05] 5.Longest Palindromic Substring (1) | 2024.02.05 |