[1스4코2파] # 171. LeetCode Pattern 49. Group Anagrams

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (171차)
[4코1파] 2023.01.13~ (163일차)
[1스4코1파] 2023.04.12~ (74일차)
[1스4코2파] 2023.05.03 ~ (53일차)

Today :

2023.06.23 [171일차]
LeetCode Patterns
1232. Group Anagrams
https://leetcode.com/problems/group-anagrams/

1232. Group Anagrams

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

문제 설명

문제 풀이 방법

문자열로 구성되어 있는 리스트인 strs가 주어졌을때,
해당 원소 문자열이 anagrams에 해당하는 것 끼리 리스트로 묶어서 return 하는 것.

anagrams애너그램은 단어나 문장을 구성하고 있는 순서를 바꾸어 다른 단어나 문장을 만드는 것임.

예를 들어 example 1 에서 'eat'의 문자열 순서를 바꾸면 'tea', 'ate' 로 바꿀 수 있는 것처럼 'eat', 'tea', 'ate' 가 anagram 묶음이다 !

해시맵으로 풀어야 하는 건 알아서,
해시맵(딕셔너리)로 만든 다음에, 해당하는 문자열을 지우고 이런 식으로 했는데
테스트 케이스 [["",""]] 에서 걸렸음.
처음 코드보면 더럽긴 한데 그래도 통과는 될 줄 알았음..

but 위 코드는

이렇게 됐다!

key로 단어를 잡았는데, 반대로 key를 문자열을 count 한걸로 잡고 value를 단어로 잡는 방법으로 바꾸면 아래 코드처럼 깔끔해지고 시간복잡도도 O(N+M) 이란다

내 코드

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        ans = defaultdict(list)
        for string in strs:
            count = [0]*26
            for s in string:
                count[ord(s)-ord('a')]+=1
            ans[tuple(count)].append(string)
        return ans.values()        

증빙

여담

간만에 easy 문제 벗어나서 medium 문제 풀기 완
금요일 코테 완완완완완완