Leetcode) Two Sum

Top Interview Questions
Easy Collection

Link of Problem

LEVEL : 🌕 🌕 🌑 🌑 🌑 (하)

---

Easy Collection의 아홉번째 문제인 Two Sum를 풀어봤습니다.

Two Sum 문제는 배열 안에 있는 두 원소의 합이 들어오는 Target과 같다면 그 두 값의 index를 배열로 return해주는 문제였습니다.

처음 생각한 방식이 시간 초과가 날 것 같아서 걱정이었는데, 생각할 수 있는 가장 기본적인 로직임에도 불구하고 시간 초과는 발생하지 않았습니다!

해당 코드말고도 생각하지 못했던 방식으로 풀어낸 방법들이 있어서 해당 코드들도 들고와봤습니다.

코드를 보면서 설명드릴게요.

1️⃣ 번째 방법

제일 기본적이고 바로 생각할 수 있는 방식이었습니다.

첫번째 원소부터 시작해서 마지막 원소까지 맞는 짝을 샅샅히 뒤지는 방식입니다.
찾아내기 위해서 이중 for문을 사용했구요. target값과 index에 해당하는 값의 차가 j에 해당하는 값과 같다면 두 수의 합이 target이라는 것이기에 [index, j]를 return해줬습니다.

기본적이기도 하고 이중for문을 사용했기 때문에 당연히 시간 초과 에러가 날 줄 알았는데, 나지 않았어요!!

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    for index in nums.indices {
        for j in index+1..<nums.count {
            if target - nums[index] == nums[j] {
                return [index, j]
            }
        }
    }
    
    return []
}

하지만 예상했던대로 Runtime이 아주 길었습니다..

2️⃣ 번째 방법

문제를 맞추자마자 가장 빠른 Runtime를 가진 답변을 찾아봤더니, 이거였습니다.

전체적으로 빠른 Runtime를 가진 답변들이 다 Dictionary를 사용했더라구요. 또 Dictionary를 응용하지 못해서 아쉬웠습니다.😫

해당 방식의 풀이는 이러합니다.

일단 nums에 있는 숫자들을 불러와서 해당 숫자가 target-num index에 해당하는 값이 있다면 그 index와 현재 index를 return하는 방식입니다.
만약에 해당하는 숫자가 없다면 Dictionary에 index와 함께 넣어주는거죠.

예를 들어, nums = [2, 7, 11, 15]이고 target = 9라면
첫번째 턴에 numDictionary[9-2]값을 찾아보겠죠? 하지만 아무것도 없기 때문에 numDictionary[2] = 0를 넣어줄겁니다.
두번째 턴에 numDictionary[9-7]값을 찾아보겠죠? 아까 넣어준 2 인덱스 값이 0이기 때문에 match = 0일 거고, 결론적으로 [0, 1]를 return할 겁니다.

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var numDictionary = [Int: Int]()
    var index = 0
    for num in nums {
        if let match = numDictionary[target - num] {
            return [match, index]
        } else {
            numDictionary[num] = index
        }
        index += 1
    }
    return []
}

Runtime 속도도 굉장히 빠릅니다.👍

3️⃣ 번째 방법

3번째 방법은 2번째 방법과 비슷하면서도 조금 다릅니다.

동일하게 Dictionary를 쓰는 건 맞지만 for문을 돌리는 방식이 달라요.
해당 방식은 nums.enumerated()를 사용했습니다. 저 방식을 사용하면 (index, num)에 해당하는 두 값이 나와요.
예를 들어서 "Swift"라는 문자열을 .enumerated()하게 된다면 [ 1: "S", 2: "w", 3: "i", 4: "f", 5: "t" ] 요렇게 된다는거죠.

저러한 방식을 사용해서 nums = [2, 7, 11, 15]에서 index와 num값을 한 번에 가져오는 겁니다.

안에서 비교하는 방식은 위와 같은데 조금 다른건 처음 비교할 때 target에서 num를 뺀 값이 아닌 그 값 자체의 index를 찾는 방식입니다. 그리고 값이 없을 때 Dictionary에 저장하는 방식도 target - num한 값에 값으로 현재의 index를 넣습니다.

위에 코드를 이해한다면 3번째 방식도 쉽게 이해할 수 있을 것이라고 생각이 듭니다.

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var complement = [Int: Int]()
    for (index, num) in nums.enumerated() {
        if let prevIndex = complement[num] {
            return [prevIndex, index]
        } else {
            complement[target - num] = index
        }
    }
    return []
}

항상 방식이 다양하게 사용할 수 있지만, 계속 배열을 쓰게 되는 거 같아요.
Dictionary나 요런 다양한 자료구조들이 조금 익숙해지면 자주 사용하게 되겠죠?😂