https://www.acmicpc.net/problem/3273
문제
> n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다.
> ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다.
> 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.접근
수열 내 두 수를 골라 두 수의 합이 x인지 보기 위해서는 이중 반복으로 수열의 각 원소를 모두 대조하며 더해보는 방법이 있지만 n의 범위가 최대 10만까진데 최악의 경우 10억번 연산해야하므로 시간초과가 난다.
따라서 수열을 입력받으며 set에 저장해두고, 수열을 한번만 순회하며 ai + aj = x를 반대로 x-ai = aj인걸 이용해서 set안에 있는지 확인한다.
이때, i,j 쌍과, j,i쌍 두번 들어가므로 /2 해준다.
문제해결
> 수열을 저장할 num 배열에 n크기로 수열을 입력받아 저장한다.
> x를 입력받고 x-i를 찾기위해 set에도 수열의 값들을 저장한다.
> 수열 num을 순회하며 x-i의 값이 set에 있는지 확인한다.
> 만족하는 경우를 누적하는데 이는 순서가 바뀐 경우도 포함이므로 중복제거를 위해 반 나눠준다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//3273번 두 수의 합
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int n, x;
public static void main(String[] args) throws IOException {
n = Integer.parseInt(br.readLine());
int[] num = new int[n];
Set<Integer> s = new HashSet<>();
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
num[i] = Integer.parseInt(st.nextToken());
s.add(num[i]);
}
x = Integer.parseInt(br.readLine());
int cnt = 0;
for(int i : num) if(s.contains(x-i)) cnt++;
System.out.print(cnt / 2);
}
}
후기
정렬 및 두 포인터로 풀 수 있다고 한다. 아마 오름차순으로 정렬하고 0,n-1번 인덱스를 각각 left,right로 잡고 left,right의 합이 x보다 크면 right를 줄이고, 작다면 left를 늘리며 누적하는것 같다.
