분류
정렬(sorting), 두 포인터(two_pointer)
문제 설명
n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)
9
5 12 7 10 9 1 2 3 11
13
출력
문제의 조건을 만족하는 쌍의 개수를 출력한다.
3
내 코드
import sys
input = sys.stdin.readline
n = int(input())
arr = sorted(list(map(int, input().split())))
x = int(input())
start, end = 0, len(arr) - 1
result = 0
while start < end:
sum = arr[start] + arr[end]
if sum <= x:
start += 1
elif sum > x:
end -= 1
if sum == x:
result += 1
print(result)-
투포인터 정리한 글 복습한 다음에 풀어서 .. 바로 풀렸다 다음에 딱 문제만 보고 풀 수 있을지 모르겠어서 조금 걱정이긴 함
-
아무튼, 구간이 연속이지 않으므로 우선 입력 받은 배열을 정렬부터 해야 함
-
정렬하고 나서 두 개의 포인터(인덱스) start와 end를 각각 양쪽 끝으로, 0과 len(arr) - 1로 초기화
-
start가 end보다 작을 동안에,
두 포인터가 가리키는 배열 값들의 합이
x보다 작거나 같으면 start 포인터를 오른쪽으로 한 칸 이동,
x보다 크면 end 포인터를 왼쪽으로 한 칸 이동
x와 같을 때는 카운트 해줌!
