[백준/Java] 3273 두 수의 합

조건

1. 수열의 개수는 N개이다.

2. 수열에서 정수의 범위는 1<= a && 1,000,000>= a 이다

3. 이때 a + a(+1) = x 가 성립하는 쌍의 수를 구해라

예제 입력

해결

수열의 앞뒤를 비교해가면서 X의 값을 찾는 것이 아닌
수열의 정수를 다 입력을 받고 이 또한 sort를 한 후 수열의 맨 앞 숫자부터 선택하여 X - A[L] 한 후 나머지 값을 찾는 이분탐색을 실행하면 이 문제는 해결할 수 있다.

코드

import java.io.*;
import java.util.*;

public class Main {
	
	static int N, ans;
	static int[] A;
	
	
	static FastReader scan = new FastReader();
	static StringBuilder sb = new StringBuilder();

	static void input() {
		
		N = scan.nextInt(); // 수열의 수를 입력받음
		A = new int[N + 1]; // Index를 1부터 시작하기 위해 +1을 해준다.
		
		for(int i=1;i<=N;i++) {
			A[i] = scan.nextInt();
		}
		
		ans = scan.nextInt(); // 수열에서 합으로 구해야하는 수
		
	}
	static boolean findAns(int[] A, int L, int R, int X) {
		while(L<=R) {
			int mid = (L + R) / 2;
			if(A[mid] == X) {
				return true;
			}
			else if(A[mid] < X) {
				L = mid + 1;
			}
			else R = mid - 1;
		}
		return false;
	}
	
	
	
	static void find() {
		Arrays.sort(A,1,N+1); // A를 정렬한다
		int count = 0;
		for(int j = 1;j<=N;j++) {
			if(findAns(A,j+ 1,N, ans -A[j])) {//이분탐색을 할때 구하는 값
            //을 X - A[] 수열 값을 넣어 A에서 해당하는 값이 있는지찾으면 된다 
           // X = A + B 는 X - A = B 로 바꿔서 계산식을 할 수 있기 때문이다.
				count++; // 해당 값을 찾으면 count ++를 해준다.
			}
			
		}

		System.out.println(count); // 쌍의 수를 출력하는 것이기 때문에 바로 								   //출력해준다.
		
	}
	
	
	public static void main(String[] args) {
		input();
		find();
	}
	
	static class FastReader{
		BufferedReader br;
		StringTokenizer st;
		
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		public FastReader(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}
		
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		Long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble(){
			return Double.parseDouble(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			}catch(IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}