hash,string,sort_LeetCode_49.GroupAnangram swift

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

문제 접근

1. 주어진 [String]매개변수를 sorted(by: >) 하여 stack에 할당 
2. !stack.isEmpty인 동안 while문 반복
3. stack의 한 요소를 비교할 대상으로 선택, 해당 요소와 크기가 같은 비교군을 생성
4. 처음 선택한 요소의 알파벳을 순차적으로 비교군에서 삭제, 결과적으로 ""가 된 idx를 얻게 됨
5. idx를 사용하여 subSol:[String]에 appned하여 anagram집합을 구함.
6. 5의 결과물을 ans: [[String]]에 append하여 최종 Return값을 준비.
7. 5에서 사용된 요소들을 stack에서 삭제.
8. 위의 내용을 반복하여 최종 return 수행

오답 코드

문제점: 매개변수 strs의 크기 및 각 요소의 크기가 커질수록 부하가 매우 커짐.

-> strs를 순회하는 method가 많기 때문.

testCase.111의 경우 문제점에 완벽히 해당함. -> 이를 해결하기 위해 hash를 사용해야 함.

class Solution {
    func groupAnagrams(_ strs: [String]) -> [[String]] {
        var stack = strs.sorted(by: >)
        var ans: [[String]] = []
        
        while !stack.isEmpty{
            
            let target = stack.removeLast()
            var tempList = stack.filter({
                $0.count == target.count
            })
            let origin = tempList
            var subSol: [String] = [target]
            
            for char in target {
                for i in 0..<tempList.count {
                    guard let index = tempList[i].firstIndex(of: char) else {
                        continue
                    }
                    tempList[i].remove(at: index)
                }
            }
            
            var emptyTarget: [String] = []
            
            for (idx,str) in tempList.enumerated() {
                if str.isEmpty {
                    emptyTarget.append(origin[idx])
                    subSol.append(origin[idx])
                }
            }
            
            var emptyIndex: [Int] = []
            
            for tgt in emptyTarget {
                guard let temp = stack.firstIndex(of: tgt) else {
                    continue
                }
                emptyIndex.append(temp)
            }
            
            
            emptyIndex.sort(by: >)
            for idx in emptyIndex {
                stack.remove(at: idx)
            }
            
            ans.append(subSol)
        }
        
        
        return ans
    }
}

정답 코드

문제 접근 : 

1. 해쉬를 위해 Dict를 사용.
2. strs의 각 요소를 sort한 값을 key로 사용하고, sort하기 이전의 요소를 value로 추가.
3. 모든 value를 array로 묶어서 반환.

 

 

func groupAnagrams(_ strs: [String]) -> [[String]] {
        var dict : [String:[String]] = [:]
        
        strs.forEach({
            let sorted = String($0.sorted(by: >))
            dict[sorted, default: []].append($0)
        })
        
        return Array(dict.values)
    }