[Java] 백준 1253 좋다

https://www.acmicpc.net/problem/1253

난이도

골드4

문제

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

입력

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

출력

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

내 코드

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

class Main {

	static int N;
	static int[] arr;

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

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

		Arrays.sort(arr);
		int ans = 0;

		for (int i = 0; i < N; i++) {
			if (isGood(i)) {
				ans++;
			}
		}
		System.out.println(ans);
	}

	public static boolean isGood(int index) {
		int target = arr[index];

		int left = 0, right = N - 1;

		while (left < right) {
			if (left == index) {
				left++;
				continue;
			}
			if (right == index) {
				right--;
				continue;
			}

			int sum = arr[left] + arr[right];
			if (sum == target) {
				return true;
			} else if (sum < target) {
				left++;
			} else {
				right--;
			}
		}
		return false;
	}
}

이분탐색으로 구현했다. 이분탐색을 하기 위해서는 입력 값들이 정렬되어 있어야 하기 때문에 가장 먼저 Arrays.sort()로 정렬을 해줬다.

그리고 배열의 하나씩 돌아가며 좋은 수인지 판별을 한다.
일반적인 이분탐색으로 목표 값이랑 같다면 바로 빠져나오고,
목표 값보다 작다면 left++, 목표 값보다 크다면 right--하면서 찾아가면 된다.
다만 left 혹은 right가 목표로 하는 index랑 같은지 확인을 해줘야 한다.