8016 : 두 수의 합
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N$개의 정수로 이루어진 배열과 목표 합 $X$가 주어집니다.
배열에서 서로 다른 두 위치의 원소를 골라 합이 정확히 $X$가 되도록 하는 두 원소의 1-기반 인덱스(위치)를 찾는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 2 \times 10^5$
• $1 \le X \le 10^9$
• $1 \le a_i \le 10^9$
배열에서 서로 다른 두 위치의 원소를 골라 합이 정확히 $X$가 되도록 하는 두 원소의 1-기반 인덱스(위치)를 찾는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N \le 2 \times 10^5$
• $1 \le X \le 10^9$
• $1 \le a_i \le 10^9$
입력 설명
첫째 줄에 두 정수 $N$과 $X$가 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개의 정수 $a_1, a_2, \ldots, a_N$이 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개의 정수 $a_1, a_2, \ldots, a_N$이 공백으로 구분되어 주어집니다.
출력 설명
합이 $X$가 되는 서로 다른 두 원소의 위치(1-based index)를 공백으로 구분하여 출력합니다. (두 위치의 출력 순서는 상관없습니다.)
만약 조건을 만족하는 쌍이 존재하지 않는다면
만약 조건을 만족하는 쌍이 존재하지 않는다면
IMPOSSIBLE을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 8
2 7 5 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2 4도움
해시 맵(딕셔너리)을 사용하여 각 원소의 값과 인덱스를 기록하면서 순회합니다.
현재 원소 $a_i$에 대해 $X - a_i$가 이미 해시 맵에 존재하면 즉시 두 위치를 출력하고 종료하여 $O(N)$ 시간에 해결할 수 있습니다.
현재 원소 $a_i$에 대해 $X - a_i$가 이미 해시 맵에 존재하면 즉시 두 위치를 출력하고 종료하여 $O(N)$ 시간에 해결할 수 있습니다.