- 문제 이해
영어를 잘하지 않아서 DeepL을 이용해 번역한 결과
대충 문자열 리스트 "strs"를 줄테니 같은 애너그램끼리 그룹화해서 제출하면 된다는 말입니다.
그룹화한 애너그램들의 순서는 신경쓰지 않고 제출하라고 쓰여있습니다.
- 애너그램 : 모든 철자를 한번만 사용하여 다른 단어를 재배열하여 형성된 단어
글로만 보면 이해가 잘 안 가서 예시 테스트 케이스를 봐보도록 합니다.
예시 1 :
입력: strs = ["eat","tea","tan","ate","nat","bat"]
출력: [["bat"],["nat","tan"],["ate","eat","tea"]]
첫번째 예제를 보니 이제 감이 오는 기분입니다.
'a'와 'b'와 't'로 이루어진 단어는 "bat" 하나뿐이니 혼자 그룹화 시켰고,
"nat", "tan"은 'a', 'n', 't' 을 이용한 단어라서 두개,
나머지 "ate, "eat", "tea"는 모두 'a', 'e', 't' 를 사용한 단어라서 묶어둔 모습인걸 알 수 있습니다.
- 풀이 과정
이제 문제를 풀어갈건데, 처음에는 visited 배열을 만들어서
문자열 하나하나 비교해서 같은 애너그램이면 체크하고 묶어서 배열을
만들고 정답에 배열을 append 하는 풀이를 생각했습니다.
그런데 그런식으로 하면 O(n^2)의 시간복잡도를 가질게 뻔했기 때문에 (2중 for문)
다른 방식이 없을까 생각했습니다.
문득 애너그램을 어떻게 구분할 수 있을까 생각을 해봤는데 생각보다 간단하게 발견했습니다.
정답은 바로 sort! 주어진 문자를 sort 하면, 애너그램이라면 똑같은 문자열이 되지 않을까?
그렇다면 sort 한 문자열이 같으면 같은 배열에 추가해주면 그룹화가 완성되겠지??
그렇게 떠오른게 딕셔너리!
딕셔너리는 간단하게 말씀드리면 {key : value}로 이루어진 자료구조인데,
이녀석은 놀랍게도 값의 입력과 추출이 O(1)의 시간복잡도를 가지는 신통방통한 친구입니다.
이것을 이용해서 sort 한 문자열을 key로 사용하고 value를 배열로
사용해서 애너그램들을 추가하고, value 값에 있는 그룹화가 완료된
친구들을 list화 해서 반환하면 아마 될 것 같습니다.
- 정답 코드
class Solution(object):
def groupAnagrams(self, strs):
dic = defaultdict(list)
# 접근하려는 key값이 없어도 exception이 발생하지 않는 딕셔너리
for i in strs :
dic["".join(sorted(i))].append(i)
# sort한 문자열을 key값으로 접근하여 원래의 문자열을 배열에 추가
return list(dic.values()) # list화 한 value값들을 반환