백준 3273번 두수의합 JAVA

풀어보진 않았지만 전체 탐색으로 합을 구하려고 하면 아마도 복잡도가 N^2이 되어서 시간복잡도가 터질 가능성이 높은 문제이다.

문제의 핵심은 두수의 합이기 때문에 더한 값이 목표하는 값보다 크다면 그 뒷부분의 값은 더할필요가 없다는 것이 핵심이다. 가장 큰값과 작은 값을 시작과 끝점으로 삼아서 합이 작다면 시작부분을 더 큰수로 교체해주고 만약 더 크다면 끝부분을 더 작은수로 줄여주며 비교해주면서 일치하는 값이 나온다면 start를 증가시키거나 end를 줄여주어서 필요없는 부분은 탐색하지 않도록 한다.

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

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

        int start=0;
        int end=0;
        int answer=0;
        int n=Integer.parseInt(br.readLine());
        numbers=new int[n];
        st = new StringTokenizer(br.readLine()," ");
        int i=0;
        while (st.hasMoreTokens()){
            numbers[i++]=Integer.parseInt(st.nextToken());
        }

        int x = Integer.parseInt(br.readLine());
        Arrays.sort(numbers);

        end=n-1;
        while (start<end&&start<n){
            if(start==end){
                start++;
            }
            if(numbers[start]+numbers[end]==x){{
                answer++;
                start++;
            }
            }else if(numbers[start]+numbers[end]<x){
                start++;
            }else if(numbers[start]+numbers[end]>x){
                end--;
            }
        }
        bw.write(Integer.toString(answer));
        bw.flush();
        bw.close();
    }
}