주제: 선형 자료구조에서 특정 조건을 만족하는 요소들의 구간 찾기
Two Pointer란?
- 투 포인터 알고리즘은 배열이나 리스트와 같은 선형 자료구조에서 특정 조건을 만족하는 요소들의 구간을 효율적으로 찾는데 사용되는 방법입니다.
- 즉, 2개의 점의 위치를 기록하면서 처리하는 알고리즘 입니다.
- 투 포인터 알고리즘을 활용해서 아래와 같은 문제들을 해결 할 수 있습니다.
- 정렬된 배열에서 특정 합을 가지는 요소 쌍 찾기
- 정렬된 배열에서 중복 제거하기
- 특정 합을 가지는 가장 긴 부분 배열의 길이 찾기
- 특정 합을 가지는 가장 작은 부분 배열 찾기
- 주어진 배열에서 최대 합 부분 찾기
- 문자열에서 첫 번째로 반복되지 않는 문자 찾기....등 등
주요 특징
- 일부 경우에는 배열이 미리 정렬되어 있어야 효율적으로 작동이 가능합니다.
- 매우 복잡한 조건이나 여러 조건을 동시에 만족해야 하는 경우에는 적용하기 어려울 수 있습니다.
동작 방식
- 투 포인터 알고리즘은 보통 두 개의 포인터를 사용합니다. 해당 포인터들은 대개 배열의 시작과 끝, 또는 특정 위치에서 시작합니다.
- 두 포인터는 특정 조건에 따라 이동하며, 한 포인터가 배열의 끝에 도달하거나 조건을 만족하는 구간을 찾을 때까지 계속합니다.
복잡도
- 투 포인터 알고리즘은 대부분의 경우 의 시간 복잡도를 가지게 됩니다. 여기서 N은 배열 또는 리스트의 길이입니다.
- 또한 추가 공간을 거의 사용하지 않으므로 의 공간 복자도를 가집니다.
구현
특정 값과 일치하는 연속된 부분 수열 찾기
func findConsecutiveSum(_ nums: [Int], target: Int) -> Int {
var start = 0
var end = 0
var sum = 0
var result = 0
while end < nums.count {
sum += nums[end]
while sum > target && start < end {
sum -= nums[start]
start += 1
}
if sum == target {
result += 1
}
end += 1
}
return result
}
let nums = [1,2,3,2,5]
let target = 5
findConsecutiveSum(nums,target)
// 3 
자연수 x가 주어졌을 때, 을 만족하는 쌍의 수 찾기 (백준 3273, S3)
- 해당 문제는 주어진 배열을 정렬하고 정렬된 배열에서 원하는 값을 찾아내는 문제이다.
- 정렬된 배열에서 주어진 값을 찾기 위해서는 두 포인터를 시작과 끝으로 정해서 시작 포인터가 끝 포인터를 넘어가기 전까지 비교해주면 된다.
import Foundation
func findSum(_ nums: [Int], target: Int) -> Int {
var start = 0
var end = nums.count - 1
var sum = 0
var result = 0
while start < end {
sum = nums[start] + nums[end]
if sum == target {
start += 1
end -= 1
result += 1
} else if sum < target {
start += 1
} else {
end -= 1
}
}
return result
}
let n = Int(readLine()!)!
let numbers = readLine()!.components(separatedBy: " ").map { Int($0)! }.sorted()
let targetSum = Int(readLine()!)!
let subCount = findSum(numbers, target: targetSum)
print(subCount)정렬된 두 리스트의 합집합 구하기
- 해당 문제는 두 배열의 각 요소를 비교하면서 작은 값을 결과 배열에 추가하면 됩니다. 두 배열 중 하나가 끝나면 남은 배열의 요소를 결과 배열에 추가합니다.
- 이 방법은 투 포인터 알고리즘의 핵심과 마찬가지로 이미 정렬되어 있을 때 효율적입니다.
func unionArray(_ arr1: [Int], _ arr2: [Int]) -> [Int] {
var i = 0
var j = 0
var result = [Int]()
while i < arr1.count && j < arr2.count {
if arr1[i] == arr2[j] {
result.append(arr1[i])
result.append(arr2[j])
i += 1
j += 1
} else if arr1[i] < arr2[j] {
result.append(arr1[i])
i += 1
} else {
result.append(arr2[j])
j += 1
}
}
while i < arr1.count {
result.append(arr1[i])
i += 1
}
while j < arr2.count {
result.append(arr2[j])
j += 1
}
return result
}
print(unionArray([1,3,3,5,7], [2,3,4,6,8]))
[1, 2, 3, 3, 3, 4, 5, 6, 7, 8]두 용액 (백준 2470, G5)
문제
- KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.
- 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.
- 예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.
- 산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.
입력
= 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.
출력
- 첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.
예제 입력 1
5
-2 4 -99 -1 98예제 출력 1
-99 98풀이
- 해당 문제를 해결했는데 계속 틀려서 확인해보니, 출력 결과를 다르게 해서 계속 틀렸음.
- 배열을 정렬한다.
- 양 끝에서 시작하는 투 포인터로 문제를 해결한다.
- right가 left을 넘어갈때까지 반복하며, 두 수의 덧샘을 변수로 설정 후 해당 변수의 절댓값이 기존 값보다 작을 시 result값을 초기화하고 두 수의 덧샘이 음수면 left +1 양수면 right -1 하면서 반복한다.
import Foundation
func findNearbyZero(_ arr: [Int]) -> [Int] {
var value = Int.max
var result: [Int] = []
var left = 0
var right = arr.count - 1
while left < right {
let tempNum = arr[left] + arr[right]
let absTempNum = abs(tempNum)
if tempNum == 0 {
result = [arr[left], arr[right]]
break
}
if value > absTempNum {
result = [arr[left], arr[right]]
value = absTempNum
}
if tempNum > 0 {
right -= 1
} else {
left += 1
}
}
return result
}
let n = Int(readLine()!)!
let arr = readLine()!.components(separatedBy: " ").map { Int($0)! }.sorted()
findNearbyZero(arr).forEach {
print($0, terminator: " ")
}출처(참고문헌)
- 이것이 코딩 테스트이다 - 나동빈
- https://medium.com/@mhcsunny/two-pointer-technique-in-swift-8f4bad8cbcbe
- https://sudarshan-sharma.medium.com/two-pointer-pattern-swift-e1e623ab9636
- https://www.acmicpc.net/problem/2470
제가 학습한 내용을 요약하여 정리한 것입니다. 내용에 오류가 있을 수 있으며, 어떠한 피드백도 감사히 받겠습니다.
감사합니다.
