✅ 문제 - 그룹 애너그램
💡 애너그램이란? 문자를 재배열하여 다른 단어로 바꾸는 것이다.
예를들어 eat의 경우 eat, ate, tea 등으로 바꿀 수 있다.
이 문제는 주어진 문자열을 이용하여 동일한 문자를 지닌 문자열들을 그룹핑해서 반환하여야 한다.
✅ 풀이 코드
from typing import List
import collections
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
#기본적으로 빈 리스트를 값으로 가지는 딕셔너리
anagrams = collections.defaultdict(list)
#str 리스트 요소에 대해 반복
#단어를 정렬, 해당 단어를 키로 하여 word를 추가함
for word in strs:
anagrams[''.join(sorted(word))].append(word)
print(anagrams)
return anagrams.values()
💡 내가 잡은 Point
1. 반환할 값을 저장하는 딕셔너리 이용(빈 리스트를 기본으로 가짐)
2. 문자열 리스트 반복문을 돌려 각 단어마다 알파벳 순으로 정렬 => 애너그램끼리 같은 값으로 반환
3. 정렬한 값을 key값으로 하는 word값 value에 추가
📌 딕셔너리란? 자바에서 HashMap과 유사
- defaultdict 객체: 존재하지 않는 키를 조회할 경우, 에러 메시지를 출력하는 대신 디폴트 값을 기준으로 해당 키에 대한 딕셔너리 아이템을 생성함
anagrams = collections.defaultdict(list)
→ 기본적으로 빈 리스트를 값으로 가짐
예를 들어,
anagrams['abc'].append('cab')
anagrams['abc'].append('bca')
이렇게 abc를 키값으로 하는 value를 cab와 bca로 추가 후 조회하면
{'abc': ['cab', 'bca']} 이렇게 확인할 수 있다.
anagrams[''.join(sorted(word))].append(word)
📌 현재 확인하고자 하는 word가 eat일 경우
sorted(word)의 결과는 ['a', 'e', 't']
.join(sorted(word)) 의 결과는 'aet'이다.
여기서 확인할 점은,
sorted에서 알파벳 순으로 정렬되기 때문에 word가 eat, ate, tea일 경우 모두 aet로 key값의 결과가 같아진다.
결과적으로 eat, ate, tea는 동일한 key값을 가지게 되며 해당 키에 value로 append해서 {'aet': ['ate', 'eat', 'tea'} 로 묶일 수 있다.
'++ > 자료구조&알고리즘' 카테고리의 다른 글
[Leetcode] 15. 3Sum (1) | 2024.01.03 |
---|---|
[Leetcode] 5. Longest Palindromic Substring (0) | 2024.01.03 |
[Leetcode] 561. Array Partition (0) | 2023.12.19 |
[프로그래머스][PCCE 기출문제] 10번 / 데이터 분석 - 250121 (0) | 2023.12.12 |
[프로그래머스][Lv.0] 짝수의 합 - 120831 (0) | 2023.12.08 |