백준 1253번 좋다 (Java)

문제

백준 1253번 좋다 / 골드4
N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 A_i가 N개 주어진다. (|A_i| ≤ 1,000,000,000, A_i는 정수)

풀이

투 포인터 문제이다. 조건을 유심히 살펴야 하는 문제이다. 우선, "어떤 수가 다른 수 두 개의 합"이라고 명시되었다. 이는 검사 할 대상 A는 A를 제외한 다른 값인 B와 C의 합이여야 된다는 의미다. 또한, "수의 위치가 다르면 값이 같아도 다른 수이다."라고 명시되었다. 그렇기에 1, 2, 3, 3, 4가 입력으로 들어와도 중복되는 3은 다른 수이다. 마지막으로, 입력 조건을 보면 번째 수를 나타내는 A_i는 정수라고 명시되었다. 그렇기에 음의 정수, 0 의 가능성을 생각해야 한다.

위 조건들을 상기하면 문제는 어렵지 않다. 우선 입력으로 받은 배열을 정렬했다. 두 수의 합의 범위를 양 끝부터 순차적으로 좁히기 위함이다. (안 해도 결괏값은 무관하다) 그리고는 배열 안의 모든 수를 비교하면 결과가 나오게 된다. 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
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));
        int N = Integer.parseInt(br.readLine());
        int[] nums = new int[N];

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

        int answer = 0;
        for (int i = 0; i < N; i++) {
            int start = 0;
            int end = N - 1;
            while (start < end) {
                int sum = nums[start] + nums[end];
                if (sum == nums[i]) {
                    if (i != start && i != end) {
                        answer++;
                        break;
                    } else if (i == start) {
                        start++;
                    } else if (i == end) {
                        end--;
                    }
                } else if (sum < nums[i]) {
                    start++;
                } else {
                    end--;
                }
            }
        }

        System.out.println(answer);
    }
}