1. 문제

---

n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는
(ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

제한 사항

시간 : 1 초
메모리 : 128 MB

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

문제의 조건을 만족하는 쌍의 개수를 출력한다.

- 키워드

• n은 최대 100,000 이므로, O(nlogn) 이내로 해결해야 한다.
• 정렬을 활용하자.

2. 풀이

---

정렬을 진행하고, 포인터를 왼쪽 끝과 오른쪽 끝에 둔다.

조건에 해당된다면 answer를 증가시키고,

두 수의 합이 조건보다 크다면 오른쪽에서,

두 수의 합이 조건보다 작거나 같다면 왼쪽에서 이동한다.

이 과정을 반복하면서 left가 right보다 커지게 되는 순간 종료한다.

3. 소스코드

---

import sys
input = sys.stdin.readline

def solution(num,result):
	left,right = 0,len(num)-1
	answer = 0
	num = sorted(num)
	while left < right:
		if num[left] + num[right] == result:
			answer += 1
		if num[left] + num[right] > result:
			right -= 1
		else:
			left += 1

	return answer

if __name__ == "__main__":
	n = int(input())
	num = list(map(int,input().split()))
	result = int(input())
	print(solution(num,result))

4. 후기

---

기업 코딩테스트에서 자주 본 것 같지는 않지만,
가끔 잊을만하다 싶으면 나오는 문제가 투포인터 문제다.
알아둔다면 언젠가 써먹을 수 있을 법하다.