3273_두 수의 합 (JAVA)

3273번: 두 수의 합

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		int[] input = new int[N];

		String str = br.readLine();
		StringTokenizer st = new StringTokenizer(str, " ");

		for(int i=0; i<N; i++){
			input[i] = Integer.valueOf(st.nextToken());
		}
		int X = Integer.parseInt(br.readLine());

		Arrays.sort(input);

		int ans = 0;
		int start = 0; int end = N-1;
		while(start<end){
			if(input[start]+input[end] == X){
				ans++;
				start++;
			}
			if(input[start]+input[end] > X)
				end--;
			if(input[start]+input[end] < X)
				start++;
		}

		bw.write(Integer.toString(ans)+'\n');
		br.close(); bw.close();
	}
}

 

정렬 + X-input[i]가 배열에 있는지 확인하는 이중 for문으로 풀면 시간초과가 난다.

 

 

[투 포인터 방법]

 

배열의 맨 앞=0, 맨 끝=N-1 를 각각 가르키며 두 원소의 합을 확인한다.

합이 X보다 크거나 작으면, start와 end를 오른쪽으로 이동(start++), 왼쪽으로 이동(end--)하면서 탐색한다.

만약 합이 X와 같으면, 카운트 해주고 탐색을 계속한다.