[Leetcode 아주 상세한 문제풀이] 49. Group Anagrams - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 49번 문제 Group Anagrams 다.

우선 문제를 살펴보자.

 

리트코드 49번 문제 Group Anagrams 링크

Group Anagrams - LeetCode

Group Anagrams - LeetCode

 

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"]]

 

Constraints:

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.

 

 

문제 설명

문제에 대해 간략히 살펴보자.

이 문제를 풀기 위해서는 우선 Anagram이 무엇인지에 대해 알아볼 필요가 있다. Anagram이란 특정 단어를 재배열 해서 만들 수 있는 단어를 말한다. 문제 예시 1번에서 보는 것처럼 "eat"이란 단어를 생각해 보자. 이 단어를 재배열 할 경우 "tea"라는 단어도 만들 수 있고 "ate"이란 단어도 만들 수 있다. 물론 이 단어들은 단순 재배열로 만들어진 '의미가 있는 단어들'이다. 따라서 eat을 재배열해서 만들어진 tea와 ate은 anagram이라고 할 수 있다.

문제로 다시 돌아가 문자열들로 이루어진 배열이 인풋으로 주어진다. 이때 anagram끼리 그룹화 하여 리턴하라는 것이 문제에서 요구하는 바다.

즉, 문제 예시 1번에서 처럼 ["eat","tea","tan","ate","nat","bat"]이 주어졌다고 생각해 보자. 이 경우 앞서 설명한대로 eat, tea, ate는 서로 anagram 이므로 한 그룹으로 묶을 수 있다. 그리고 nat과 tan 역시 anagram 이므로 한 그룹으로 묶인다. 마지막으로 bat의 경우 anagram이 존재하지 않으므로 그 자체로 그룹이 된다. 결과적으로 6개의 문자열은 3개의 같은 anagram 그룹으로 묶을 수 있다. 요약하면 입력된 문자열들을 anagram 그룹화 하여 출력하라는 것이다.

 

 

문제 접근법

이 문제에서 요구하는 것은 anagram인 단어끼리 그룹화를 하는 것이다.

따라서 dictionary를 이용하여 그룹을 만들 수 있다.

그렇다면 주어진 단어들에서 어떻게 anagram인 단어들을 찾을 수 있을 것인가?

Anagram의 특성에 대해 곰곰히 생각해 보면 답을 찾을 수 있다.

가장 중요한 anagram의 특성은 단어들을 알파벳 순으로 정렬했을 때 같아진다는 것이다.

예를 들어 앞서 anagram임을 알아 봤던 eat, tea, ate의 경우를 생각해 보자.

이 세 단어 모두 알파벳 순으로 정렬했을 때 모두 aet가 된다는 것이다.

다시 말하면 주어진 단어들을 알파벳 순으로 정렬했을 때 같은 단어가 된다면 그 단어는 anagram이다.

문제 풀이에 핵심이 되는 아이디어에 대해 설명했으니 이제 코드로 알아보자.

 

 

문제 풀이

문자 배열을 입력받기 위한 함수를 정의해 준다. (line 1)

문제에서 요구하는 것처럼 anagram인 단어들 끼리 그룹화하기 위해 dictionary를 만들어 준다. (line 2)

문제 접근법에서 설명한대로 우선 주어진 단어들을 알파벳 순으로 정렬해준다.

그리고 그것들을 dictionary의 key로 사용하기 위해 tuple에 넣어준다. (line 6-8)

그 key들이 anagram dictionary에 존재하지 않을 경우 dictionary에 추가해준다. (line 12)

이제 dictionary에 key가 들어갔으므로 인풋으로 주어진 문자열을 dictionary에 넣어준다. (line 15)

물론 이때 해당 key값에 해당하는 곳에 넣어줘야 한다.

이 과정을 반복하다보면 anagram의 경우 정렬 후 같은 key 값을 갖기 때문에,

dictionary 안에서 같은 key 값으로 그룹화가 된다.

입력된 모든 문자열을 dictionary에 넣어준 후 그 dictionary의 value 값을 리턴해주며 종료한다. (line 18)

 

 

문제 풀이 코드

def groupAnagrams(strs):
    # Create an empty dictionary to store the anagrams
    anagrams = {}
    
    # Iterate over each string in the input list
    for s in strs:
        # Sort the string and use it as a key
        key = tuple(sorted(s))
        
        # If the key is not in the dictionary, add it with an empty list as its value
        if key not in anagrams:
            anagrams[key] = []
        
        # Append the original string to the list corresponding to its sorted version
        anagrams[key].append(s)
    
    # Return the values (lists of anagrams) from the dictionary
    return list(anagrams.values())
 
# Test cases
strs1 = ["eat","tea","tan","ate","nat","bat"]
print(groupAnagrams(strs1))  # [["bat"],["nat","tan"],["ate","eat","tea"]]
 
strs2 = [""]
print(groupAnagrams(strs2))  # [[""]]
 
strs3 = ["a"]
print(groupAnagrams(strs3))  # [["a"]]