[LeetCode] #1 Two Sum - Swift 풀이

노션에서 보기

0001 Two Sum

 

문제

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

(예시 생략)

---

 

요약하자면 합해서 target이 되는 nums Array의 두 수를 찾고,

그 수들의 index를 찾아서 리턴하라는 것이다.

 

코드스쿼드 알고리즘 2주차 문제로 주어진 건데 사실 이 문제는 2달 전 Swift를 거의 처음 배울 때 시도한 적이 있었다.

그땐 하다가 안돼서 포기했더랬다🥲

지금 보니 이게 왜 안됐지 싶다

하지만 이번엔 20분 내외로 성공! (와!)

그간 실력이 늘었다는 사실에 소소하게 기뻐하며 이제 진짜 풀이를 정리해보겠다.

풀이

1. 중첩 루프

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var arr = nums
    let cnt = arr.count

    for i in 1...cnt {
        let first = arr[cnt-i]

        for j in 0..<cnt-i {
            let second = arr[j]

            if first + second == target {
                return [cnt-i, j]
            }
        }
    }
    return []
}

이 풀이는 정말 별게 없다.

순회하면서 수를 하나 집고 (first), 그 수 및 지나온 수들을 제외한 수에서 또 하나 집은 다음 (second)

두 수의 합이 target과 일치하면 index를 배열로 만들어서 리턴하면 끝.

루프에서 끝끝내 리턴하지 못했다면 빈 배열을 돌려주면 함수가 마무리 된다.

 

너무 단순무식(?)한 풀이라 아쉬웠는데 우선 다음 문제를 풀어야 해서 이정도로 마무리를 하고,

다른 문제들을 푼 다음 다시 풀어봤다.

 

2. 보수와 딕셔너리 활용

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

    var dics = [Int:Int]()

    for i in 0..<nums.count {
        dics[nums[i]] = i
    }

    for j in 0..<nums.count {
        let complement = target - nums[j] //보수 구하기
        let cIdx = dics[complement] //보수에 해당하는 nums의 인덱스값 가져오기
        if cIdx != nil && cIdx != j { return [cIdx!, j]}
    }
    return []
}

어렴풋이 a = target - b를 활용해보면 어떨까 생각은 했는데

target - b를 넣은 새 배열을 만들었다가, 너무 비효율적으로 진행돼서 이건 아니다 싶었다.

그리고 solution을 보니, hash table에 관한 이야기가 있길래 자세한 코드는 안 보고 후다닥 덮은 다음 구현을 해보았다.

 

루프를 활용한 1번 풀이의 시간 복잡도는 O(n²)인 반면, 이 풀이는 O(n)이다.

하지만 n개의 요소가 담긴 딕셔너리가 생기므로 공간복잡도는 O(n)이 된다. 1번은 O(1).