스위프트 코딩테스트 강좌, 투 포인터

문제 설명

주어진 정수 배열 nums가 있을 때, 이 배열에서 서로 다른 두 인덱스 i와 j에 대해 nums[i] + nums[j] == target이 되는 인덱스 쌍의 모든 조합을 찾아 반환하시오.
단, 같은 숫자는 두 번 사용할 수 없으며, 인덱스 쌍 (i, j)와 (j, i)는 동일한 조합으로 간주하여 중복해서 취급하지 말아야 한다.

예를 들어, 배열 nums = [2, 7, 11, 15]이고 target = 9일 때, 반환해야 할 인덱스 쌍은 [0, 1]입니다.
이는 nums[0] + nums[1] = 2 + 7 = 9이기 때문입니다.

문제 분석

이 문제를 해결하기 위해서는 효율적인 방법이 필요합니다. 일반적으로 이중 반복문을 사용할 경우, 시간 복잡도는 O(n^2)가 되며 대규모 배열에 대해서는 비효율적입니다.
따라서 우리는 투 포인터 기법을 활용하여 시간 복잡도를 O(n)으로 줄이는 방법을 소개하겠습니다.

투 포인터 기법 이해하기

투 포인터 기법은 배열을 처리할 때 유용한 알고리즘 기법으로, 두 개의 포인터를 사용하여 문제를 해결하는 방식입니다. 이 기법을 통해 우리는 배열의 복잡한 문제를 단순화할 수 있습니다.
간단한 예를 들어보겠습니다. 정렬된 배열에서 두 수의 합이 특정 값(target)과 같아지는 모든 조합을 찾고 싶다고 가정해 보겠습니다.

초기에 두 포인터를 하나는 배열의 시작, 다른 하나는 배열의 끝에 위치시킵니다. 두 포인터가 가리키는 값의 합이 target보다 크면 오른쪽 포인터를 이동시켜 줄입니다.
반대로 합이 target보다 작으면 왼쪽 포인터를 이동시킵니다. 이렇게 포인터를 조정함으로써 모든 가능한 조합을 확인할 수 있습니다.

문제 해결 과정

문제를 해결하기 위한 과정을 단계적으로 설명하겠습니다.

1단계: 배열 정렬

투 포인터 기법을 적용하기 위해서는 배열을 정렬해야 합니다. 정렬을 진행하면 보다 쉽게 각 포인터에 대한 값을 비교하고 이동할 수 있습니다.
정렬된 배열에서 각 숫자는 더 빨리 찾을 수 있으며, 중복된 조합도 방지할 수 있습니다.

2단계: 포인터 초기화

포인터를 초기화합니다. 하나는 시작 위치(0 인덱스), 다른 하나는 끝 위치(배열 길이 – 1)에서부터 시작합니다.

3단계: 합 비교 및 포인터 이동

– 포인터가 서로 교차할 때까지 반복합니다.
– 현재 포인터들이 가리키는 숫자의 합이 target보다 크면, 오른쪽 포인터를 하나 왼쪽으로 이동시킵니다. (즉, 더 작은 값을 선택)
– 합이 target보다 작으면, 왼쪽 포인터를 하나 오른쪽으로 이동시킵니다. (즉, 더 큰 값을 선택)
– 합이 target과 같으면, 인덱스를 기록하고, 두 포인터를 각각 이동합니다.

4단계: 결과 반환

모든 가능한 조합을 찾은 후에, 인덱스 쌍의 목록을 반환합니다.

Swift 코드 구현

다음은 위에서 설명한 알고리즘을 스위프트로 구현한 코드입니다.

swift
import Foundation

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

    for (index, num) in nums.enumerated() {
        let complement = target - num
        if let complementIndex = numDict[complement] {
            result.append([complementIndex, index])
        }
        numDict[num] = index
    }

    return result
}

// 사용 예시
let nums = [2, 7, 11, 15]
let target = 9
let indices = twoSum(nums: nums, target: target)
print(indices) // Output: [[0, 1]]

결론

투 포인터 기법은 시간 복잡도를 줄이고, 더 나은 성능을 제공하는 강력한 도구입니다. 이 기법은 많은 알고리즘 문제에서 유용하게 사용될 수 있으며,
특히 배열의 두 숫자 합을 찾는 문제에서 매우 효과적입니다.
이 강좌를 통해 스위프트 언어로 알고리즘 문제를 해결하는 방법을 배우고, 더 나아가 다양한 문제를 해결할 수 있는 능력을 배양하길 바랍니다.

추가 연습 문제

다음의 문제들을 풀어보세요.

정렬된 배열에서 두 수의 합이 특정 값이 되는 모든 인덱스 쌍 찾기
정렬된 배열에서 고유한 쌍의 개수 세기
누적 합이 특정 값인 모든 구간 찾기
주어진 숫자가 포함된 구간 내 모든 쌍 찾기