Swift) LeetCode(Easy) - Two Sum (Dictionary)

leetcode.com/problems/two-sum/

Two Sum - LeetCode

안녕하세요! 후르륵짭짭 입니다!

LeetCode라는 곳을 알게 되어 처음으로 문제를 풀어보고 싶어서 쉬운 것을 풀어봤습니다.

문제는 간단합니다.

그냥 두개의 숫자를 더해 목표 값의 위치 두개를 반환 하면 됩니다. 대신 같은 위치에서 두번 더하면 안됩니다.

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    
    for ele1 in 0..<nums.count{
        
        for ele2 in (ele1+1)..<nums.count{
            
            if nums[ele1] + nums[ele2] == target && nums[ele1] != nums[ele2]{
                return [ele1, ele2]
            }
            
        }
    }
    
    return []
}

처음에는 이렇게 2중 포문으로 풀었습니다. 

이렇게 풀면 시간 복잡도가 O(N^2)이 되기 때문에 효율적이지 못합니다.

 

그래서 시간 복잡도를 O(nLog^n)을 가질 수 있는 딕셔너리를 사용해야합니다.

func twoSum2(_ nums: [Int], _ target: Int) -> [Int] {
    
    var dic : [Int : Int] = [:]
    
    for index in 0..<nums.count{
        dic[index] = nums[index]
    }
    
    for index in 0..<nums.count{

        let findValue = target - nums[index]
        
        let valueArray = dic.filter { (element) -> Bool in
            
            if element.key == index{
                return false
            }
            
            return element.value == findValue
        }
       
        if valueArray.count != 0 {
            return [index, valueArray.first!.key].sorted()
        }

    }

    return []
}

이러한 방법을 한 이유는  딕셔너리의 key 값을 index로 한다면 중복을 피할 수 있기 때문입니다.

그래서 후에 filter로 찾아야하는 값이 있는 것만 분류해서 반환을 해줬는데,

이러한 방법은 이유가 먼지 모르겠지만 시간초과가 발생 했습니다.... (N^2이 발생 안했는데,,,)

 

결국 고민 끝에

func twoSum3(_ nums: [Int], _ target: Int) -> [Int]{
    
    var dic : [Int : Int] = [:]
    
    for (index, val) in nums.enumerated(){
        
        let need = target - val
        
        if let index2 = dic[need]{
            return [index, index2].sorted()
        }
        
        dic[val] = index
    }
    
    return []
}

이렇게 코드를 짜면

목표 값에서 현재 인덱스의 값을 빼면 필요한 값이 나옵니다.

그리고 딕셔너리에 그 값이 있는지 확인하고 정렬해서 반환하면 됩니다.

처음에는 이 방법이 될까 의심스러웠는데, 생각해보니 됐습니다.

 

왜냐하면 현재 index 값은 추가해주지 않기 때문이고 나중에 넣어주기 때문입니다.

예를 들어

목표값이 4고 배열이 [2,1,2]라고 할때

2 -> 딕셔너리는 []

1 -> 딕셔너리 [2]

2 -> 딕셔너리 [2,1]

이렇게 때문에 중복을 피할 수 있씁니다.

 

참고로!!!

if let으로 딕셔너리가 존재하는지 아닌지 구분해줄 수 있습니다!

developer.apple.com/documentation/swift/dictionary/2995335-filter

Apple Developer Documentation