7034 : 두 수의 합 (Two Sum)
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 1
•통과: 1
•만든사람: suakii
문제 설명
서로 다른 정수들로 구성된 리스트와 목표하는 합 $T$가 주어집니다.
리스트의 서로 다른 두 원소를 더해서 합이 $T$가 되는 쌍(Pair)의 개수를 구하는 프로그램을 작성하십시오.
단, 쌍을 이룰 때 두 원소의 순서만 바뀐 것은 같은 쌍으로 봅니다. (예: $(1, 8)$과 $(8, 1)$은 1개로 취급)
[제약 조건]
• 리스트 크기 $N$: $1 \le N \le 100{,}000$
• 목표 합 $T$: $-10^9 \le T \le 10^9$
• 각 정수 원소: $-10^9 \le a_i \le 10^9$
리스트의 서로 다른 두 원소를 더해서 합이 $T$가 되는 쌍(Pair)의 개수를 구하는 프로그램을 작성하십시오.
단, 쌍을 이룰 때 두 원소의 순서만 바뀐 것은 같은 쌍으로 봅니다. (예: $(1, 8)$과 $(8, 1)$은 1개로 취급)
[제약 조건]
• 리스트 크기 $N$: $1 \le N \le 100{,}000$
• 목표 합 $T$: $-10^9 \le T \le 10^9$
• 각 정수 원소: $-10^9 \le a_i \le 10^9$
입력 설명
첫째 줄에 리스트의 크기 $N$과 목표 합 $T$가 공백으로 구분되어 주어집니다. ($1 \le N \le 100000$, $-10^9 \le T \le 10^9$)
둘째 줄에 서로 다른 $N$개의 정수가 공백으로 구분되어 주어집니다. 각 정수는 $-10^9$ 이상 $10^9$ 이하입니다.
둘째 줄에 서로 다른 $N$개의 정수가 공백으로 구분되어 주어집니다. 각 정수는 $-10^9$ 이상 $10^9$ 이하입니다.
출력 설명
두 수의 합이 $T$가 되는 서로 다른 쌍의 개수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 9
1 3 5 6 8
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
배열을 오름차순 정렬한 뒤 맨 앞과 맨 뒤를 가리키는 두 포인터(Two Pointer)를 이용해 합을 좁혀가거나, 해시셋(Set) 또는 해시맵(Dictionary)을 사용해 현재 값 $x$에 대해 $T - x$가 이전에 등장했는지 $O(1)$에 체크하는 방식으로 전체 $O(N)$에 해결할 수 있습니다.