N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
수의 위치가 다르면 값이 같아도 다른 수이다.
첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)
좋은 수의 개수를 첫 번째 줄에 출력한다.
두 개의 숫자를 골라서 더한 값이 주어진 input 에 있어야 하며 그와 동시에 우리가 고른 두 숫자가 아니여야 합니다.
우리는 두 가지 방식을 쉽게 떠올릴 수 있습니다. 첫 번째는 두 개의 반복문을 돌며 모든 조합을 찾는 것 입니다. 1 번의 조건이 없었다면 좋겠지만 우리는 두 숫자가 더한 숫자이면 안된다는 것을 알기 때문에 코드로 도출하기 골치아픕니다. 또한 해당 방식은 O(n^2) 의 효율을 가집니다.
두 번째 방식은 이분 탐색입니다. 우리는 이제 모든 입력값을 찾는 이분 탐색을 진행할 것입니다. for 문으로 현재 값을 찾고 해당 값을 더할 수 있는 두 숫자를 찾습니다. 해당 방식은 O(nlogn)의 효율을 가집니다.
⚠️주의할 점⚠️
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;
}
}