[JAVA] 백준 1253 투포인터

1253번: 좋다

문제

주어진 수 배열에 대해서 배열의 값 X가 다른 배열의 두 값의 합으로 나타낼 수 있다면 “좋다”라고 표현한다.

주어진 배열에 대해서 좋은 수는 몇개인지 출력하시오.

풀이

주어진 값들을 정렬한다면 대상 값의 앞에 까지만 합을 계산해봐도 해당 값이 합으로 나타낼 수 있는지 알 수 있다.

따라서 먼저 수들을 정렬하고 배열의 첫번째 부터 대상 값의 바로 앞 까지의 값을 투포인터로 비교하면 된다.

start값과 end값의 합을 구하고 대상 값보다 작다면 start값을 높이고 크다면 end 값을 낮춘다.

만약 대상 값과 같다면 다음 값을 대상으로 반복한다.

유의해야할 부분은 같은 값이 배열에 존재할 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        long[] S = new long[N];
        for(int i=0; i<N; i++){
            S[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(S);

        int answer = 0;

        for(int i=0; i<N; i++){
            int start = 0;
            int end = N-1;
            while(start < end){
                long sum = S[start] + S[end];
                if(sum < S[i]) start++;
                else if(sum > S[i]) end--;
                else{
                    if(start != i && end != i){
                        answer++;
                        break;
                    }else if(start == i){
                        start++;
                    }else if(end == i){
                        end--;
                    }
                }
            }
        }
        System.out.println(answer);



    }

}

결과