49. Group Anagrams

Yunes·2022년 6월 13일

Top Interview 150 golang leetcode python 난이도: Medium 알고리즘

알고리즘 및 코딩테스트

목록 보기

7/23

Problem

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 은 "adc" "dca" "cad" 등처럼 어순만 다르고 구성하고 있는 문자들이 동일한 문자열을 뜻합니다. 본 알고리즘 문제는 여러 문자열 리스트가 주어지고 각 문자열들을 읽어 동일 Anagram 끼리 묶어 이를 반환하라는 문제입니다.

해결방법

Anagram 인지 여부는 어떻게 알 수 있을까?

이에 대한 고민을 해보았을때 처음엔
1. 두 문자열을 비교하여 Anagram 인지 여부를 확인하는 함수를 짜자
2. 슬라이스의 문자열을 순서대로 읽어 처음이라면 슬라이스에 넣고, 해당 문자열을 해시맵의 key, value 에 넣자
3. 처음이 아니라면 Anagram group 생성되어있는 해시맵의 key 들과 비교하여 일치하면 해당 문자열을 value 에 추가하고 기존 key 들과 겹치지 않는다면 새로운 group 의 key, value 에 추가한다.

이런 아이디어로 코드를 구성했다.

좀 조잡한 느낌도 들지만 대부분의 케이스에서 리턴이 정상적으로 나타났다.

하지만 leetcode 서밋 마지막에 굉장히 긴 문자열을 테스트 케이스로 보이더니 코드 실행시간 초과로 리턴값이 나타나지 않았다. 아무래도 for 문이 중첩되며 isAnagram 역시 반복문을 사용하여 O(n^2) 보다도 더 오래 걸려 시간이 많이 소요된다는 부분이 마음에 걸렸다.

이후 고민해보다가 생각난게 Anagram 여부를 두 문자열로 비교할게 아니라 hash map 의 key 에는 문자열을 abc 순으로 정렬된 값을 넣고 value 에는 string 을 넣어주면 해결되리라 생각했다.

그래서 주어진 문자열 슬라이스를 for 반복문으로 읽고 각 문자열의 문자 배치를 사전순으로 정렬해주는 함수를 따로 짠뒤, 읽은 문자열의 정렬된 문자를 key로, value 에 정렬되지 않은 문자열을 append 로 넣는다면 key 는 중첩될 수 있으나 value 는 겹치지 않을 것이고(이건 가정이었으나 애초에 완전히 동일한 문자는 등장하지 않을 것이라 생각했다.) 그럼 그렇게 구한 2차원 슬라이스를 반환하면 되겠다고 생각했다.

Answer

그렇게 해서 구한 코드는 다음과 같다.

하단의 SortString 은 문자열 정렬을 검색해서 stackoverflow 에서 본 함수를 그대로 가져다 썼다.
처음에 이게 되는 것을 보고 slice 에 append 할때 동일한 문자열이 들어가도 ["1", "1", "2"] 이렇게 될텐데 map에선 mapName["test"] = ["1","2"] 이렇게 되나 생각했는데 map 역시도 value 의 중복값을 자체적으로 없애주는 기능은 없었다. 다만 예시로 주어진 anagram 후보 문자열 중엔 완전히 동일한 문자열이 없었다.

Result

Python 풀이

js 로 알고리즘 준비를 하다보니 백준에서 node.js 입출력이 너무 불편한 것도 있고 코테에서 js 가 나오지 않는 경우도 종종 있으니 알고리즘 연습을 파이썬으로 하고자 한다.

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        output = []
        wordDict = {}
        for word in strs:
            sortedWord = ''.join(sorted(word, key=str.lower))
            if sortedWord not in wordDict:
                wordDict[sortedWord]=[]
            wordDict[sortedWord].append(word)

        for key in wordDict:
            output.append(wordDict[key])
        return output