투 포인터
오늘은 백준 단계별로 풀어보기에서 투 포인터 부분을 풀 차례이다.
투 포인터 개념 자체가 크게 어렵지 않아서 여기에 있는 5문제 모두 풀었다.어렵지 않더라도 개념자체는 많은 곳에서 효율적으로 쓰일 수 있는 알고리즘이라 정확하게 이해하고 어느 부분에 쓰일 수 있을지를 파악하는게 중요할 것 같다.
투 포인터(Two Pointers)
-
리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
-
1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 특정 조건을 만족하는 부분 구간을 효율적으로 탐색하는 알고리즘이다.
-
보통의 문제에서는 정렬되어있을 때 사용하지만 가끔 정렬하지 않아야 하는 조건이 주어진 문제에서는 그대로 투 포인터로 활용하여 풀어야한다.
-
배열의 정렬 상태와 문제의 목적에 따른 두 접근 방식이 있다.
-
두 포인터의 시작점을 0과 1또는 둘 다 0에서 시작하며 조건에 따라 end와 start를 증가시키는 방법.
- 이 방식은 주로 정렬되지 않은 배열에서 두 수의 합, 차, 곱, 비 등을 특정 값과 비교하여 조건을 만족하는 요소의 쌍을 찾을 때 사용된다. 포인터 하나는 고정하고 다른 하나를 이동시키면서 모든 가능한 조합을 탐색한다.
- 주로 특정합을 만족하는 두 요소의 쌍 찾기(정렬되지 않은 배열에서)에서 사용된다.
- 배열에 정렬되어 있지 않아도 적용 가능하지만, 모든 가능한 쌍을 확인해야 하므로 시간 복잡도가 O(N^2)에 달할 수 있다는 특징을 가지고 있다.
-
두 포인터를 양 끝에서 시작하며 end를 감소시키거나 start를 증가시키는 방법.
- 이 방식은 정렬된 배열에서 사용된다. 배열의 양 끝에서 시작하여 중앙으로 포인터를 이동시키면서, 조건을 만족하는 요소의 쌍을 찾거나, 특정 합/차에 가장 가까운 요소의 쌍을 찾는데 사용된다.
- 이 방식은 정렬된 배열에서 두 요소의 합이 특정 값에 가장 가까운 요소의 쌍 찾기, 두 요소의 합이 특정 값을 초과하지 않는 최대값 찾기 등에서 주로 사용된다.
- 정렬된 배열에서 사용되며, 두 포인터를 이동시키는 로직에 따라 O(N) 시간 복잡도를 가지며 문제를 해결한다.
-
BaekJoon 3273번 : 두 수의 합 (S3 34.567%)
해당 문제는 n개의 서로 다른 양의 정수로 이루어진 수열중 a[i] + a[j] = X를 만족하는 (i,j)쌍의 수를 구하는 문제이다.
주어진 조건에서 n은 100000이하이다.
기존에 브루트포스를 이용하여 문제를 풀었으면 시간복잡도가 O(N^2)으로 시간초과가 걸렸을 문제이다.
- 수열의 길이 n과 수열, target값을 입력 받는다.
- 투 포인터를 이용해 시간 복잡도 O(N)으로 풀기 위하여 입력받은 수열을 정렬시킨다.
- 투 포인터를 양 끝에 위치시켜 비교를 하기 시작한다.
- arr[start] + arr[end] < target 경우 두 수의 합을 늘려주어야 하기 때문에 start의 포인터를 1 증가시켜준다.
- arr[start] + arr[end] > target 경우 두 수의 합을 줄여줘야 하기 때문에 end 포인터를 1 감소시켜준다.
- arr[start] + arr[end] == target 경우 count+=1을 해주고 start를 증가시키거나 end를 감소시켜준다.(이 때 둘 중 하나라도 변화를 시켜줘도 괜찮다. 만약 변화가 없다면 무한루프에 빠지게 된다.)
- 진행하다 start와 end가 같아지는 순간 서로 다른 두 정수의 합을 구할 수 없는 상태이기에 while문을 빠져나오게 된다.
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int,input().split()))
target = int(input())
arr.sort()
s = 0
e = n-1
count = 0
#print(arr)
while s< e :
if arr[s] + arr[e] == target :
count += 1
s+=1
if arr[s] + arr[e] < target :
s += 1
if arr[s] + arr[e] > target :
e -= 1
print(count)
owei