대충 이분탐색인 것까지는 예상을 했는데(딱 봤을 때 골드5에서 브루트포스는 아닐거고, 그래프도 아니고, dp도 아니고, 그리디도 아니고, 스택/큐/힙도 아니고, 그럼 남은건 이분탐색이니까), 잘 안돼서 진짜진짜 마지막으로 이것만 보자는 마음으로 알고리즘 분류를 눌렀는데 투포인터...는 초면이네? (아직도 새로운게 나와.. 엉엉)
(스포 : 이분탐색만으로도 풀 수 있었는데 난 못했다.. 바보다)
말그대로 2개의 포인터를 이용해서 문제를 해결하는 알고리즘이다.
1차원배열에서 두 개의 포인터를 이용해 탐색하면서 원하는 결과를 얻는데, 반복문을 사용한 기존의 방식보다 시간과 메모리의 효율성을 높일 수 있다.
앞에서 시작하는 포인터와 끝에서 시작하는 포인터가 만나는 형식
빠른 포인터가 느린 포인터보다 앞서가는 형식
문제에 따라 어떤 포인터를 쓸지 잘 생각해봐야 한다.
투포인터에 대해 찾아보다가 한방에 이해가 잘됐던 문제다.
수열
A[1], A[2], …, A[N]
의i
번째 수부터j
번째 수까지의 합A[i] + A[i+1] + … + A[j-1] + A[j]
가M
이 되는 경우의 수를 구하시오.
M=5일때의 동작과정을 보자.
e
를 증가시키는 것은 더할 수를 늘리는 것이고, s
를 증가시키는 것은 더할 수를 줄이는 것이다. 문제상황에 따라 적절히 변형하면 된다.
이렇게 투포인터 알고리즘을 사용하면 반복문을 매번 돌리지 않아도 O(N)
의 시간복잡도로 문제를 해결할 수 있다.
투포인터 알고리즘을 이용하면 모든 경우의 수를 셀 수 있으며, 꼭 배열이 정렬되어 있지 않아도 사용 가능하다.
import sys
input = sys.stdin.readline
N = int(input())
sol = list(map(int, input().split()))
p1 = 0
p2 = N-1
s = 2000000000
while p1 < p2:
mix = sol[p1]+sol[p2]
if abs(mix) < abs(s):
answer = [sol[p1], sol[p2]]
s = mix
if mix < 0:
p1 += 1
else:
p2 -= 1
print(answer[0], answer[1])
포인터 종류는 앞에서 시작하는 포인터와 끝에서 시작하는 포인터가 만나는 형식이다.
두 포인터가 가리키는 값의 합이 최소값이면 정답을 갱신한다.
두 포인터가 가리키는 값이 음수일때는 0에 가까워지기 위해서는 수를 키워야하니까 앞포인터를 늘리고, 양수일때는 0에 가까워지기 위해 수를 줄여야하니까 뒤포인터를 줄인다.
이진탐색은 뭘까 싶어서 찾아봤더니 이렇게 모든 용액에 대해서 내 다음 용액부터 끝까지를 범위를 잡고 이진탐색을 총 n-1번 수행하는 방법도 있었다. 큰틀은 투포인터랑 매우 비슷하다.
(안돌려봄 그냥 로직만 참고)
import sys
input = sys.stdin.readline
N = int(input())
sol = list(map(int, input().split()))
s = 2000000000
for i in range(n-1):
current = sol[i]
start = i + 1
end = n - 1
while start <= end:
mid = (start + end) // 2
mix = current + sol[mid]
if abs(mix) < abs(s):
answer = [sol[p1], sol[p2]]
s = mix
if mix < 0:
start = mid + 1
else:
end = mid - 1
print(answer[0], answer[1])