백준 3273번: 두 수의 합 [정렬][두 포인터][구현] - Java

문제가 단순하여 2중 for문을 바로 떠올리겠지만

시간제한이 1초이기 때문에, 좀 더 고민해봐야한다. (시간복잡도 O(N^2)인데, N이 1 <= N <= 100000)임

100000*100000하면 100억 됨 (10,000,000,000)..

1초당 1억연산이 가능하다고 생각하면 됨..

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		int result = 0;

		// 입력받기
		int N = Integer.parseInt(st.nextToken());

		int[] arr = new int[N];
		int[] exist = new int[1000001];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			exist[arr[i]]++;
		}

		st = new StringTokenizer(br.readLine());
		int X = Integer.parseInt(st.nextToken());

		// 함수실행
		for (int i = 0; i < N; i++) {
			if (arr[i] == X)
				continue;
			int need = X - arr[i];
			if (1 <= need && need <= 1000000) {
				if (exist[need] > 0)
					result += exist[need];
			}
		}
		System.out.println(result / 2);
	}

}