[BOJ 1253] 좋다 (Java)

문제

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

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

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

입력

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

출력

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

접근 방법

1. 두 개의 숫자를 골라서 더한 값이 주어진 input 에 있어야 하며 그와 동시에 우리가 고른 두 숫자가 아니여야 합니다.

2. 우리는 두 가지 방식을 쉽게 떠올릴 수 있습니다. 첫 번째는 두 개의 반복문을 돌며 모든 조합을 찾는 것 입니다. 1 번의 조건이 없었다면 좋겠지만 우리는 두 숫자가 더한 숫자이면 안된다는 것을 알기 때문에 코드로 도출하기 골치아픕니다. 또한 해당 방식은 O(n^2) 의 효율을 가집니다.

3. 두 번째 방식은 이분 탐색입니다. 우리는 이제 모든 입력값을 찾는 이분 탐색을 진행할 것입니다. for 문으로 현재 값을 찾고 해당 값을 더할 수 있는 두 숫자를 찾습니다. 해당 방식은 O(nlogn)의 효율을 가집니다.

⚠️주의할 점⚠️

• 2번 방식을 구현한 코드도 찾아 볼 수 있습니다. 하지만 해당 방식은 0 그리고 동일 숫자가 중복해서 들어오는 경우를 면밀히 생각하지 않으면 오류가 날 수 있으므로 주의해야 합니다.

소스 코드

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

public class Good {

    static int[] numbers;
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        numbers = new int[n];
        String[] input = br.readLine().split(" ");
        int result = 0;

        for (int i = 0; i < n; i++) {
            numbers[i] = Integer.parseInt(input[i]);
        }

        Arrays.sort(numbers);

        for (int i = 0; i < n; i++) {
            if (find(i)) {
                result++;
            }
        }
        System.out.println(result);
    }

    public static boolean find(int cur) {
        int number = numbers[cur];
        int lt = 0, rt = n - 1;

        while (lt < rt) {
            if (lt == cur) {
                lt++;
                continue;
            }
            if (rt == cur) {
                rt--;
                continue;
            }
            if (numbers[lt] + numbers[rt] < number) {
                lt++;
            } else if (numbers[lt] + numbers[rt] > number) {
                rt--;
            } else {
                return true;
            }
        }
        return false;
    }
}

결과