Anagrams 아나그램 알고리즘
Anagrams 아나그램 알고리즘 — #LeetCode #개발자의도구들 #Anagrams #아나그램 #아나그램알고리즘 #상수배시간복잡도 #문자열정렬 #딕...
#LeetCode#Naver Blog
#LeetCode #개발자의도구들 #Anagrams #아나그램 #아나그램알고리즘 #상수배시간복잡도 #문자열정렬 #딕셔너리이중배열
- only 파이썬
- 목표 참고 : 여기
anagrams 전략 생각하기
LeetCode(medium 49. Group Anagrams) 70.5%
⚠️ n : 1..10000
>>> t: 최대 o(n²) -> 간당간당..
📌 예전에 비슷한 문제를 푼 적 있다.
🤔 글자를 붙여서 나열하는 전략
>>> nice의 anagrams를 구한다고 가정해보자
✅ nicenice이렇게 붙여놓는다.
>>> 가능한 문자열은 nice -> icen -> ceni -> enic 이다.
✅ for str in strs:
>>> str을 읽어들인 후 anagram을 만들어서 set에 등록해둔다.
>>> 이후 문자열들에 대해서 set에 포함되면 skip
>>> 없다면, 다시 문자열을 만들어 set에 포함한다.
⌛ time: O(n²) n번의 순회에 최대 n개의 문자열이 만들어진다.
📦 space: O(n) 최대 n개의 원소를 포함하는 set이 만들어진다.
1차 시도
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
result = []
anagrams = set()
for word in strs:
if word not in anagrams:
# make anagrams
tmp = word + word
mid = len(tmp) // 2
res = []
for i in range(mid):
test = tmp[i: i + mid]
if test not in anagrams:
anagrams.add(test)
res.append(test)
result.append(res)
# append to result
else:
continue
return result
# lemonlemon
- ❌ 오답이다.
- ant 와 tan도 동일 그룹으로 봐야한다.
- ant를 거꾸로 한 단 어의 anagrama도 합쳐야 진정한 anagram이 완성된다.
- 만들어진 anagrams내에서 strs에 등록된 요소만 그룹핑 해야한다.
로직 수정하기
✅ anagram만들때 뒤집은 글자도 만들어주기
✅ Check를 위한 그룹과 result용 그룹을 따로 둬서 필터링을 수행하자.
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
result = []
check = []
anagrams = set()
for word in strs:
if word not in anagrams:
# make anagrams
tmp = word + word
mid = len(tmp) / 2
group1 = []
for i in range(mid):
test = tmp[i: i + mid]
if test not in anagrams:
anagrams.add(test)
group1.append(test)
group2 = []
rtmp = tmp[::-1]
for i in range(mid):
test = rtmp[i: i + mid]
if test not in anagrams:
anagrams.add(test)
group2.append(test)
check.append(group1 + group2)
# filtering
for chk in check:
group = []
for ans in chk:
if ans in strs:
group.append(ans)
result.append(group) if len(group) > 0 else result.append([""])
return result
- ❌ 오답이다.
- filtering을 이렇게 두닌깐 좀 많이 복잡하다.
- 로직을 좀 더 단순화 해보자.
📦 전체 pivot관리 + 지역 pivot관리
✅ for word in strs:
>>> i == 0 인 지점에 set과 group을 만든다.
>>> set을 만들어서 해당 단어의 모든 anagram을 set에 등록한다.
>>> for j in range(i, n):
>>> strs[j]가 set에 포함되면 group에 넣는다.
>>> i !=0인 지점부터는...
>>> 전체 pivot에 속해있으면 바로 continue
3차시도 ...
로직이 잘못된 것을 깨달아 버림
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
if len(strs) == 1:
return [[strs[0]]]
result = []
pivot = set()
n = len(strs)
for idx, word in enumerate(strs):
if word not in pivot:
group = [word]
local = set()
# make local set and global set
tmp = word + word
rtmp = tmp[::-1]
mid = len(tmp) / 2
for i in range(mid):
anagram = ""
for t in tmp[i: i + mid]:
anagram += t
local.add(anagram)
pivot.add(anagram)
for i in range(mid):
anagram = ""
for t in rtmp[i: i + mid]:
anagram += t
local.add(anagram)
pivot.add(anagram)
for n in strs[idx + 1:]:
if n in local:
group.append(n)
result.append(group)
else:
continue
return result
- 역시 오답이다.
- 이쯤 되닌깐 내가 잘못 접근한게 아닌가 의심이 들었다.
- 👉 알고보니 anagram이 글자의 순열을 의미하는 것이였다.
순열인지 확인하는 방법
✅ 순열인지 확인하려면 두 문자 간의 문자 별 문자 갯 수가 일치하는지 확인 하면 된다.
>>> Counter를 사용하자
🤔 그룹으로 어떻게 나눌까?
>>> 글자를 set에 담아두자.
>>> 그 글자로부터 이후 값을 미리 체크하여 그룹을 만든다.
>>> 체크된 부분은 '-'처럼 영문자가 아닌 것으로 변경해주면 된다.
from collections import Counter
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
result = []
n = len(strs)
for i, word in enumerate(strs):
if word == "-":
continue
else:
group = [word]
# check counter
for j in range(i + 1, n): # 이건 새로운 list라서 ...
next_word = strs[j]
if Counter(word) == Counter(next_word):
group.append(next_word)
strs[j] = "-"
result.append(group)
return result
- 오답이다 ❌❌
- Time limit이 걸린다.
- Grouping이 왜이리도 어려운 것인가...
O(n)을 향해서...
🤔 딕셔너리를 사용해보자.
>>> O(n)이 될 수 있겠다.
🤔 어차피 중복되지 않는 순열 key값 하나만 가지고 있으면 되지않나??
✅ dict 선언
✅ word를 dict의 key로 두고 list를 value로 관리하기.
from collections import Counter
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
result = []
n = len(strs)
anagrams = {}
for word in strs:
if word not in anagrams:
if len(anagrams) == 0:
anagrams[word] = [word]
else:
exist = False
for key in anagrams:
if Counter(key) == Counter(word):
ans = anagrams[key]
ans.append(word)
anagrams[key] = ans
exist = True
if not exist:
anagrams[word] = [word]
else:
ans = anagrams[word]
ans.append(word)
anagrams[word] = ans
for key in anagrams:
result.append(anagrams[key])
return result
- dictionary를 사용해도 결국 O(n²)이다...
- 이제는 못하겠다.
정답 로직
with gpt 4o
🤔 기존 코드는 왜 틀렸을까?
✅ counter의 시간복잡도를 고려하지 않았다.
>>> key의 크기가 k라고 가정하면, counter는 매번 O(k)만큼의 시간이 소모된다.
>>> 📌 고로 내가 작성한 로직은 계속해서 O(n² * k)의 시간복잡도를 가지는 것이다...
>>> O(n * klogk)으로 줄여보자.
>>> 🙅♂️ 시간복잡도에 대해서 혼동이 있는 상태: 아래에 정확히 적어놓았다.
✅ Anagram의 특징은 정렬시 두 단어가 같아진다는 것이다.
>>> counter 대신 정렬을 사용해서 비교하면 문제를 해결할 수 있다.
from collections import Counter
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
result = []
strs_s = strs[:]
for i, word in enumerate(strs_s): #O(n)
l_word = list(word) #O(nlogn)
l_word.sort()
strs_s[i] = str(l_word)
anagrams = {}
for idx, word in enumerate(strs_s): #O(n)
if word in anagrams:
anagrams[word].append(idx)
else:
anagrams[word] = [idx]
for key in anagrams:
idxs = anagrams[key]
group = []
for idx in idxs:
group.append(strs[idx])
result.append(group)
return result
- 드디어 해결했다...
- t: O(n \* nlogn) ❌❌ 35.70 Beats
- s: O(n \* k)
- 너무나 많은 전략이 있었지만, 접근을 잘못해서 오래걸렸다.
- 시간 복잡도에 대해서는 아래 정확히 적어두었다.
여러가지 코드 오답
for i, word in enumerate(strs):
print("word: ", word)
if word == "-":
continue
else:
group = [word]
# check counter
🚫❌for next_idx, next_word in enumerate(strs[i + 1:]): # 이건 새로운 list라서 ...
print("next_idx", next_idx)
if Counter(word) == Counter(next_word):
group.append(next_word)
strs[next_idx] = "-"
print("changed next_idx: ", next_idx, strs[next_idx])
print("group: ", group)
result.append(group)
- 원하는 로직: next\_idx가 i부터 시작
- 실제로직: next\_idx가 0부터 시작함
- strs\[i+1:\]은 새로운 리스트로 되기 때문이다.
counter의 시간 복잡도는 O(k)이다.
👉 시간복잡도 분석에 대해서
✅ 이번 문제의 핵심은 O(n²) -> O(n)으로 시간을 줄이는 것에 있다.
🤔 여기서 중요한것은 n과 k를 구분하는 것이다.
>>> n의 경우 strs, 즉 입력값 자체이다.
>>> k의 경우에는 strs의 각 요소 즉 실제 단어들이다.
>>> 이는 문제에서 0..100의 크기를 가진다고 되어있다.
>>> 이 말은 k는 매우 작은 크기를 가지고 있으므로, 거의 무시된다.
>>> 적당히 상수배로 보면된다.
>>> 📌 이는 상대적인 수치이므로, n에 비해서 매우 작은 경우만 해당 됨
✅ 결론적으로 각 word를 정렬하는 것은 Klogk만큼의 시간 복잡도가 소모되고, 이는 매우 작은 값이다.
>>> 결국에 시간 복잡도는 O(n * klogk)로 O(n)으로 봐도 무방하다.!!
# 문자열 정렬 시에는
sorted(word)
# defultdict로 코드 줄이기
anagrams = defaultdict(list) # key가 없다면 해당 키를 등록 후 빈 리스트([])를 자동 등록
# 자동 등록한 상태에서 바로 append 기능 사용가능!
for word in strs:
sorted_word_list = sorted(word)
# abc => ['a', 'b', 'c']
key = ''.join(sorted_word_list)
# .join은 list의 각 값을 사이에 ''를 넣어 string으로 변환한다.
anagrams[key].append(word)
# dict 각 value (list)를 담아서 이중 배열 return
return list(anagrams.values())