[Leetcode/Easy] 두 수의 합 (1. Two Sum, Swift)

2024. 7. 1. 16:10Algorithm

https://leetcode.com/problems/two-sum/description/

 

🤔 문제 설명

덧셈하여 타깃 숫자를 만들 수 있는 배열의 두 숫자 인덱스를 반환하세요.

입력된 nums에는 정확히 하나의 답이 있다고 가정하며, 또한 동일한 요소를 두 번 사용하지 않는다고 가정합니다.
답은 임의의 순서로 반환할 수 있습니다.

[2,7,11,15], target = 9
// [0,1]

 

🧑🏻‍💻 첫 번째 풀이와 코드 (Swift ver.)

단순하게 중첩 반복을 사용하기보다, 한 번의 반복에서 한 값을 가지고 target-num으로 나머지 한 값을 찾는 방법을 생각했다.

값은 array.firstIndex(of: target-num) 문법을 사용해서 찾을 수 있었고,
자기 자신을 찾는 경우는 생략하기 위해 조건을 한 가지 더 추가했다. (inIndex: 찾아야 하는 인덱스 != index: 기존 인덱스)

Runtime : 72ms (Beats 10.52%), Memory : 16.21MB (Beats 61.13%)

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        for (index, num) in nums.enumerated() {
            if let inIndex = nums.firstIndex(of: target-num), inIndex != index {
                return [index, inIndex]
            }
        }
        return []
    }
}

 

🧑🏻‍💻 개선된 풀이와 코드 (Swift ver.)

딕셔너리를 사용하면, 코드를 더 개선할 수 있다.

타깃값을 찾는 것은 똑같으며, 그 인덱스를 직접 firstIndex로 찾는 것이 아니라 저장해둔 딕셔너리에서 꺼내두는 것만 변경했다.

Runtime : 16ms (Beats 94.25%), Memory : 16.62MB (Beats 7.96%)

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var numToIndex = [Int: Int]()   // Num: Index
        
        for (index, num) in nums.enumerated() {
            if let complementIndex = numToIndex[target-num] {
                return [complementIndex, index]
            }
            numToIndex[num] = index
        }
        
        return []
    }
}