[1253] 좋다 (JAVA)

# 문제 설명

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

---

입력

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

---

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

 

# 정답 코드

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

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

        int N = Integer.parseInt(st.nextToken());
        int[] A = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int n = 0; n < N; n++) {
            A[n] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(A);

        int cnt = 0;

        for (int num = 0; num < A.length; num++) {
            int start = 0;
            int end = N - 1;

            while (start < end) {
                if (A[start] + A[end] == A[num]) {
                    if (start != num && end != num) {
                        cnt++;
                        break;
                    }
                    else if (start == num) {
                        start++;
                    }
                    else if (end == num) {
                        end--;
                    }
                }
                else if (A[start] + A[end] > A[num]) {
                    end--;
                }
                else {
                    start++;
                }
            }
        }

        System.out.println(cnt);
    }
}

 

수의 개수 N과 N개의 숫자들을 입력받아 배열 A에 저장한다.

좋은 수의 개수를 cnt에 저장한다.

 

숫자의 크기를 조절하기 쉽도록 배열 A를 오름차순 정렬한다.

for문으로 A의 숫자들을 순회하며 num이 좋은 수인지 검사한다.

start는 배열의 첫번째 인덱스 0으로, end는 배열의 마지막 인덱스 N-1으로 설정한다.

 

start와 end가 교차되기 전까지 while문을 반복한다.

• 만약 A[start]와 A[end]의 합이 A[num]과 같고 start와 end가 num과 다른 수인 경우, cnt를 1 증가하고 다음 num으로 넘어간다.
• A[start]와 A[end]의 합이 A[num]과 같지만 start나 end가 num과 같으면 좋은 수가 아니므로 start를 증가시키거나 end를 감소시킨다.
• A[start]와 A[end]의 합이 A[num]보다 크면, end를 감소시킨다.
• A[start]와 A[end]의 합이 A[num]보다 작으면, start를 증가시킨다.