정수 배열과 목표 정수가 주어졌을 때, 두 수의 합이 목표 값이 되는 두 수의 인덱스를 반환한다.
이 문제에는 다양한 해결 방법이 있으며, 어떤 방법은 다른 방법보다 더 효율적이다. 다음 해결 방법들은 모두 O(n) 시간 복잡도를 가진다.
이 해결책은 한 번에 하나의 숫자를 살펴보며, 각 숫자를 딕셔너리에 저장한다. 숫자를 키로 사용하고, 배열에서의 인덱스를 값으로 저장한다.
각 숫자 n에 대해, 타겟과 합쳐지는 보완 숫자는 target - n이다. 딕셔너리에서 보완 숫자를 조회하면, 이전에 보완 숫자를 본 적이 있는지와 그 인덱스가 무엇인지 알 수 있다.
func twoSum(_ nums: [Int], target: Int) -> (Int, Int)? {
var dict = [Int: Int]()
// 모든 숫자 n에 대해,
for (currentIndex, n) in nums.enumerated() {
// 타겟과 합쳐지는 보완 숫자를 찾는다.
let complement = target - n
// 딕셔너리에서 보완 숫자가 있는지 확인한다.
if let complementIndex = dict[complement] {
return (complementIndex, currentIndex)
}
// n과 그 인덱스를 딕셔너리에 저장한다.
dict[n] = currentIndex
}
return nil
}twoSum 함수는 두 개의 매개변수를 받는다: numbers 배열과 타겟 합계. 이 함수는 타겟과 합쳐지는 두 요소의 인덱스를 반환하거나, 찾을 수 없으면 nil을 반환한다.
알고리즘이 어떻게 동작하는지 살펴보자. 주어진 배열은 다음과 같다:
[3, 2, 9, 8]합이 10이 되는 두 항목이 있는지 찾아보자.
초기에는 딕셔너리가 비어 있다. 각 요소를 반복하며 진행한다:
보완 숫자 7이 딕셔너리에 있는가? 아니므로, 3과 그 인덱스 0을 딕셔너리에 추가한다.
[3: 0]보완 숫자 8이 딕셔너리에 있는가? 아니므로, 2와 그 인덱스 1을 딕셔너리에 추가한다.
[3: 0, 2: 1]보완 숫자 1이 딕셔너리에 있는가? 아니므로, 9와 그 인덱스 2을 딕셔너리에 추가한다.
[3: 0, 2: 1, 9: 2]보완 숫자 2이 딕셔너리에 있는가? 있다! 이는 타겟과 합쳐지는 두 항목을 찾았다는 의미다.
따라서, complementIndex = dict[2] = 1이고 currentIndex = 3이다. 반환하는 튜플은 (1, 3)이다.
주어진 배열에 여러 해결책이 있다면, 첫 번째 해결책만 반환한다.
이 알고리즘의 실행 시간은 **O(n)**이다. 배열의 모든 요소를 살펴볼 수 있기 때문이다. 또한 딕셔너리를 위한 O(n) 추가 저장 공간이 필요하다.
참고: 이 알고리즘은 배열이 정렬되어 있어야 한다. 배열이 정렬되지 않았다면(보통 그렇다), 먼저 정렬해야 한다. 알고리즘 자체의 시간 복잡도는 **O(n)**이며, 이전 해결책과 달리 추가 저장 공간이 필요하지 않다. 물론, 먼저 정렬해야 한다면 전체 시간 복잡도는 **O(n log n)**이 된다. 약간 더 느리지만 여전히 괜찮은 성능이다.
다음은 Swift로 작성한 코드다:
func twoSumProblem(_ a: [Int], k: Int) -> ((Int, Int))? {
var i = 0
var j = a.count - 1
while i < j {
let sum = a[i] + a[j]
if sum == k {
return (i, j)
} else if sum < k {
i += 1
} else {
j -= 1
}
}
return nil
}첫 번째 해결책과 마찬가지로, twoSumProblem() 함수는 숫자 배열 a와 찾고자 하는 합 k를 매개변수로 받는다. 합이 k가 되는 두 숫자가 있다면, 함수는 해당 숫자들의 배열 인덱스를 포함한 튜플을 반환한다. 그렇지 않으면 nil을 반환한다. 주요 차이점은 a가 정렬되어 있다고 가정한다는 점이다.
테스트하려면 코드를 플레이그라운드에 복사하고 다음을 추가한다:
let a = [2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100]
if let (i, j) = twoSumProblem(a, k: 33) {
a[i] + a[j] // 33
}이 코드는 튜플 (8, 10)을 반환한다. a[8] = 12이고 a[10] = 21이기 때문에, 두 숫자를 더하면 33이 된다.
이 알고리즘은 어떻게 동작할까? 이 알고리즘은 배열이 정렬되어 있다는 점을 활용한다. 많은 알고리즘에서도 마찬가지로, 데이터를 먼저 정렬하면 계산이 더 쉬워지는 경우가 많다.
예제에서 정렬된 배열은 다음과 같다:
[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]
알고리즘은 두 변수 i와 j를 사용해 배열의 시작과 끝을 가리킨다. 그런 다음 i를 증가시키고 j를 감소시키며 두 포인터가 만날 때까지 반복한다. 이 과정에서 a[i]와 a[j]의 합이 k가 되는지 확인한다.
과정을 단계별로 살펴보자. 처음에는 다음과 같다:
[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]
i j
두 숫자의 합은 2 + 100 = 102다. 이 예제에서 k = 33이므로 이 값은 너무 크다. 100은 절대 답이 될 수 없으므로 j를 감소시킨다.
다음과 같이 변경된다:
[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]
i j
이제 합은 2 + 22 = 24다. 이 값은 너무 작다. 이 시점에서 2는 절대 답이 될 수 없다는 결론을 내릴 수 있다. 오른쪽의 가장 큰 숫자는 22이므로, 왼쪽에는 최소 11이 필요하다. 11보다 작은 숫자는 답이 될 수 없다. (이 때문에 배열을 정렬한 것이다!)
따라서 2는 제외하고 i를 증가시켜 다음 작은 숫자를 확인한다.
[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]
i j
합은 3 + 22 = 25다. 여전히 너무 작으므로 i를 다시 증가시킨다.
[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]
i j
사실, 12에 도달할 때까지 i를 몇 번 더 증가시켜야 한다:
[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]
i j
이제 합은 12 + 22 = 34다. 이 값은 너무 크므로 j를 감소시킨다. 결과는 다음과 같다:
[ 2, 3, 4, 4, 7, 8, 9, 10, 12, 14, 21, 22, 100 ]
i j
마침내 답을 찾았다: 12 + 21 = 33.
물론, a[i] + a[j]가 k가 되는 값이 없을 수도 있다. 그 경우, 결국 i와 j가 같은 숫자를 가리키게 된다. 그러면 답이 없다고 결론 내리고 nil을 반환한다.
이 작은 알고리즘은 매우 매력적이다. 입력 데이터에 대한 기본적인 전처리(낮은 값에서 높은 값으로 정렬)만으로도 복잡한 문제를 간단하고 아름다운 알고리즘으로 바꿀 수 있다는 것을 보여준다.
Swift Algorithm Club을 위해 Matthijs Hollemans와 Daniel Speiser가 작성했으며, Farrukh Askari가 Swift 4.2로 업데이트함