[Swift] LeetCode #01. Two Sum

문제링크

문제 요약

• Input 으로 받아오는 배열 중 2개의 요소를 더한값이 Target 의 값과 같을때, 그 요소의 인덱스를 리턴해주는 함수를 작성해라. (반환값의 인덱스 순서는 상관없음)

문제 공략

자료구조

• 2중 for loop 을 구현해서 합이 Target 이 되는 인덱스를 반환한다.
  -> O(n^2) 의 시간 복잡도 를 가지게됨.
• Dictionary 를 사용하여 문제 공략
  -> O(n) 시간 복잡도

접근방식

• "두요소의 합이 target 의 값과 같아야한다" 라는 문장에서 어떻게 하면 딕셔너리를 사용해서 문제를 풀수 있을까 고민하게됨.
• 아래와같이 (Target - value) 의 나머지 값이 딕셔너리에 존재할경우 해당 인덱스 를 찾아 반환해주도록 구현.

//Given : nums = [3,2,4], Target = 6

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var originalDict : [Int: Int] = [:]

    for (index, value) in nums.enumerated(){
        //nums 를 딕셔너리 로 변환  [값 : 인덱스] 
        originalDict.updateValue(index, forKey: value)
    }

    for (index, value) in nums.enumerated(){
        let leftover = target - value
        // 남아있는 값이 diff 딕셔너리 키에 존재하고, 그 key 의 value 가 현재 인덱스가 아니라면 
        //(현재 index, 즉 6-3 = 3 인데 diff 배열의 자신의 인덱스를 가르키면 안돼기때문에 이케이스는 무시해야한다.)
        if originalDict[leftover] != nil && (originalDict[leftover] != index){
            return([index, originalDict[leftover]!])
        }
    }
    return []
}

문제 회고

• Guard let 을 사용해서 if 문을 더 간단하게 구현가능
• 딕셔너리에 오리지널 값을 넣는게 아닌, target-nums[index] 값을 키로 넣어줌

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var diffDict : [Int: Int] = [:]

    for (index, value) in nums.enumerated(){
        guard let resultIndex = diffDict[value] else { 
        // diffDict = [뺀 나머지값 : 순서]
            diffDict[target-value] = index
            continue
        }
        return [index , resultIndex]
    }
    return []
}