•
문제 설명
n개의 서로 다른 양의 정수 으로 이루어진 수열이 있다.
이때 인 자연수이다.
자연수 가 주어졌을 때, 을 만족하는 쌍의 수를 구한다.
•
풀이 방법
모두 탐색하기에는 의 시간복잡도가 사용된다. 이는 시간초과의 위험이 있기 때문에 투 포인터를 사용한다.
를 기준으로 양쪽 포인터를 이동하여, 두 쌍의 합을 줄이거나 키워야한다. 이를 위해서는 숫자의 목록을 정렬해야한다.
왼쪽 지점은 가장 작은 수에서, 오른쪽 지점은 가장 큰 수에서 시작하여 사용한다.
두 쌍의 합 → 왼쪽 지점을 큰 수의 방향으로 옮겨 두 쌍의 합을 키운다.
두 쌍의 합 → 오른쪽 지점을 작은 수의 방향으로 옮겨 두 쌍의 합을 줄인다.
이렇게 하는 이유는, 양 지점을 모두 수열의 범위 안에서 이동하기 위해서이다.
만약 두 쌍의 합을 키우기 위해 왼쪽 지점이 아닌 오른쪽 지점을 옮긴다면 수열의 범위를 벗어날 가능성이 있다. (IndexError 발생)
left : 왼쪽 → 오른쪽으로만 이동하기 때문에, left의 위치가 수열의 길이보다 큰 index가 되기전에 right를 만나면서, IndexError를 막는다.
right : 오른쪽 → 왼쪽으로만 이동하기 때문에, right의 위치가 0보다 작은 index가 되기전에 left를 만나면서, IndexError를 막는다.
•
성공 코드
N = int(input())
info = list(map(int, input().split()))
search = int(input())
answer = 0
# 오름차순 정렬
info.sort()
# 투 포인터를 이용
left = 0
right = N - 1
# 두 지점이 만나기 직전까지
while left < right:
# 합을 줄이기 위해 right를 왼쪽으로 이동
if info[left] + info[right] > search:
right -= 1
# 합을 키우기 위해 left를 오른쪽으로 이동
elif info[left] + info[right] < search:
left += 1
# 같을 경우, left를 오른쪽으로 이동
# answer += 1
elif info[left] + info[right] == search:
answer += 1
left += 1
print(answer)
Python
복사