투포인터 알고리즘 Swift

투포인터 알고리즘

- 리스트에 순차적으로 접근할 때 두 원소의 위치를 기록하는 알고리즘

- 일반적으로 정렬된 리스트나 배열에서 사용한다.

- 보통 정해진 두 위치(첫번째: start, 마지막:end)는 start <= end를 만족한다.

 

 

투포인터 단계

- 배열또는 리스트에 두개의 위치를 지정한다(보통 맨 앞 위치 start, 맨 뒤 위치 end)

- 두 포인터 사이의 구간을 확인하고 조건과 비교한다.

- 해당 조건을 만족한다면, 추가로 위치를 움직이거나, 결과를 리턴한다.

- 해당 조건을 만족하지 않는다면, 위치를 움직여 재탐색후 조건과 비교한다.

 

시간복잡도: 포인터를 배열이나 리스트의크기(N)만큼 증가시키므로 O(N)

 

예시: BOJ-2470 두 용액

import Foundation

// 입력받기
let N = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{Int(String($0))!}
var result = Int.max
var resultArr = [Int]()
var start = 0
var end = arr.count - 1
arr.sort(by: <)

// 왼쪽인덱스 start, 오른쪽인덱스 end가 서로 만날때 까지
while start < end {
    let leftNum = arr[start]
    let rightNum = arr[end]
    let sum = leftNum + rightNum
    
    // 더한값이 양수라면 오른쪽인덱스를 왼쪽으로 움직여 오른쪽 원소값을 더 작게만든다
    // 더한값이 음수라면 왼쪽인덱스를 오른쪽으로 움직여 왼쪽 원소값을 더 크게만든다.
    if sum > 0 {
        end -= 1
    } else if sum < 0 {
        start += 1
    } else {
        resultArr = [leftNum, rightNum]
        break
    }
    // 더한값의 절댓값이 이전에 구한 값보다 작아지면 갱신
    if abs(sum) < result {
        result = abs(sum)
        resultArr = [leftNum, rightNum]
    }
    
}
print(resultArr.map{String($0)}.joined(separator: " "))