[LeetCode] Group Anagrams

문제 링크 >> https://leetcode.com/problems/group-anagrams/

 

 

📋 문제

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

 

 

👉 입출력

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

 

Example 2:

Input: strs = [""]
Output: [[""]]

 

Example 3:

Input: strs = ["a"]
Output: [["a"]]

 

 

💡 사용된 개념

✔️ join()

이터러블의 모든 요소들을 구분자를 통해 하나의 문자열로 만든다.

 

string.join(iterable)

• string : separator. iterable 요소들을 붙일 때 사용하는 구분자.
• iterable : 요소들을 붙일 iterable 객체

 

 

📝 풀이

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        answer = []
        hashmap = {}
  
        for i in strs:
            temp = "".join(sorted(i))
            temp_arr = []
            
            if temp in hashmap:
            	# 아나그램이 존재함
                hashmap[temp].append(i)
            else:
                temp_arr.append(i)
                hashmap[temp] = temp_arr
  
        for v in hashmap.values():
            answer.append(v)
            
        return answer

 

문제에서 original letter들을 한번씩만 사용한다고 했으니 모든 문자열에는 중복되는 문자가 존재하지 않는다.

따라서 문자열의 각 문자들을 쪼개 오름차순으로 정렬한 후 다시 하나의 문자열로 만들어 temp에 저장했다.

 

그리고 이 temp를 hashmap에 저장하는데 hashmap에 temp라는 key가 없으면 key에 temp, value에 원본 문자열을 저장했다.

만약 temp가 이미 hashmap의 key로 존재한다는 것은 해당 문자열의 아나그램이 이미 hashmap에 저장된 것이다.

따라서 이때는 hashmap[temp]에 현재 원본 문자열을 추가한다.

 

이 과정을 거치고 나면 hashmap에는 같은 문자 구성을 가지고 있는 아나그램들이 문자 구성별로 구분되어 value에 저장된다.

따라서 hashmap의 value들을 answer에 저장, 리턴시켜 주었다.

 

 

+++

문제가 영어라서 그런지 문제를 안 읽고 그냥 예제만 보고 풀려고 하다가 자꾸 뻘짓하게 된다.

이번에도 original letter들을 한번씩만 사용한다는 것을 나중에 봤다.

그래서 여러 문자들이 존재하는 경우의 수까지 다 하다가 멘탈 터지는 줄 알았다.

꼭 문제 먼저 읽기 제발 좀!

 

 

 

🔍 참조

join() https://www.w3schools.com/python/ref_string_join.asp