swift 리트코드 문제풀이 - leetcode 49 그룹 애너그램

swift 리트코드 문제풀이 - leetcode 49 그룹 애너그램

 

leetcode 49. Group Anagrams

 

문제

문자열 배열을 받아 애너그램 단위로 그룹핑을 하세요.

 

예제

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

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

 

 

일단 애너그램이라는 용어가 생소할 수 있는데, 쉽게말하면 하나의 단어가 있으면 이 단어의 문자를 재배열 해서 다른 뜻을 가진 새로운 단어로 바꾸는 것임. [nat, tan] 을 보면은 a, n, t 문자가 하나씩 똑같이 들어있는것을 알 수 있음. 그리고 순서만 바뀌어서 그룹핑되어 있다는 것을 캐치할 수 있음.

 

그래서 단순히 떠오르는 아디어는 입력 받은 문자열 배열의 문자들을 전부 오름 차순으로 정렬하는것임! 어차피 단어의 개수도 같고 단어를 구성하는 문자도 같기 때문에! 

 

사실 오름차순으로 정렬해도되고, 내림차순으로 정렬해도됨. 취향대로

 

그리고 단어를 그룹핑하기 전단계로

1.오름차순으로 정렬되어 있는 단어들을 비교해서

2.같은 단어들을 체크한다음

3.같은 단어들의 위치(index)를 먼저 그룹핑 한 다음

4.위의 index 를 이용해서 해당 위치의 단어를 찾은 다음 그 단어들을 그룹핑 해주면 될것 같음!

 

위의 아이디어와 흐름을 이용해서 아래와 같은 코드를 작성했음.

 

var groupAnagramsStr = ["eat","tea","tan","ate","nat","bat"]
//Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

func groupAnagrams(_ strs: [String]) -> [[String]] {
    
    var resultArray : Array<Array<String>> = []
    
    //타입 Annotation으로 딕셔너리 생성하기
    var tempDic: [String: Array<Int>] = [:]
    
    //배열안의 문자들을 오름차순으로 정렬
    let sortedArray = strs.map{ String($0.sorted(by: < )) }
    
    print("sortedArray :  \(sortedArray) " )
    
    //애너그램 문자 : [해당 문자의 배열 index...] 로 딕셔너리 만들기
    for (index, word) in sortedArray.enumerated(){
        let keys = tempDic.keys.filter{ $0.elementsEqual(word) }
        (keys.count > 0) ? (tempDic[word]?.append(index)) : (tempDic[word] = [index])
    }
    
    print("tempDic :  \(tempDic) " )    //["ant": [2, 4], "abt": [5], "aet": [0, 1, 3]]

    //좋은예 : 빠름!
    for groupArray in tempDic.values {
        resultArray.append( groupArray.map{ strs[$0] } )
    }
    
    //나쁜예 : 느림!
    /*
     for groupArray in tempDic.values {
         var strGroupArr : Array<String> = []
         for idx in groupArray {
             strGroupArr.append(strs[idx])
         }
         resultArray.append(strGroupArr)
     }
     */
    
    return resultArray
}
print(">>>> groupAnagrams :\( groupAnagrams(groupAnagramsStr) )")
//>>>> groupAnagrams :[["bat"], ["tan", "nat"], ["eat", "tea", "ate"]]

 

위에보면 좋은예, 나쁜예 주석을 달아놨음. 나쁜예로 작성해도 상관은 없음. 하지만 입력 문자열 배열의 요소가 수천개일 경우에 속도 이슈가 생김! 그래서 입력 받을 수 있는 문자열 배열안의 요소가 최대 몇개인지 먼저 파악하고 몇개 안되면 for문으로 가도 되고, 만약 swift 에서 dictionary도 value 값들을 for in 문으로 돌려서 접근할 수 있고, map을 이용해서 배열안의 내용을 재구성 할 수 있다는 지식이 있다면 for in, map 등을 사용해서 풀어도 좋다!

 

 

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