문제
https://www.acmicpc.net/problem/1253
N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
수의 위치가 다르면 값이 같아도 다른 수이다.
입력
첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)
출력
좋은 수의 개수를 첫 번째 줄에 출력한다.
예제 입력 1
10
1 2 3 4 5 6 7 8 9 10
예제 출력 1
8
접근
일단 기본적으로 숫자들이 랜덤하게 배열되어 있으면 무조건 처음부터 끝까지 다 탐색을 할 수밖에 없으니 정렬을 해야 하는 건 당연하다고 생각했다.
1차 시도
그래서 정렬을 한 것까지는 좋았는데
처음에 예제 입력만 보고 음수가 주어지는 경우는 생각도 안 하고 구현을 했었다... i번째 수가 좋은지 확인하기 위해 0번째부터 i-1번째 수까지만 탐색을 했던 것.
입력으로 주어지는 수가 모두 0 이상일 때는 당연히 i번째 수보다 큰 수를 탐색하는 건 의미가 없다. 하지만... i번째 수가 음수일 때는 0번째부터 i-1번째 수가 모두 음수일테니 이 범위에 있는 어떤 두 수를 더해도 i번째 수보다 작다. 그러니 이땐 오히려 i+1번째 수부터 끝까지의 범위를 탐색해야 한다.
예를 들어 입력을 정렬한 결과가 1 3 5 8 10일 때, 8이 좋은 수인지 확인하려면 8보다 왼쪽에 있는 수들을 탐색해 3+5=8임을 알아내야 한다.
반대로, 입력을 정렬한 결과가 -10 -8 -7 -4 -3일 때, -7이 좋은 수인지 확인하려면 -7보다 오른쪽에 있는 수들을 탐색해 -4+(-3)=-7임을 알아내야 한다.
아무튼,,, 처음에는 이걸 간과하고 무조건 현재 수의 왼쪽에 있는 수들만 탐색했다가 틀렸다. 처음 틀렸던 코드는 다음과 같다.
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
long[] arr = new long[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Long.parseLong(st.nextToken());
}
if (N < 3) {
System.out.println(0);
return;
}
Arrays.sort(arr);
Set<Long> cache = new HashSet<>();
int count = 0;
if (arr[0] == arr[1] + arr[2]) {
count++;
}
if (arr[1] == arr[0] + arr[2]) {
count++;
}
for (int i = 2; i < N; i++) {
boolean flag = false;
if (cache.contains(arr[i])) {
flag = true;
}
int j = i - 2;
for (; j >= 0 && arr[i - 1] + arr[j] > arr[i]; j--) {
cache.add(arr[i] + arr[j]);
}
if (j >= 0 && arr[i - 1] + arr[j] == arr[i]) {
cache.add(arr[i - 1] + arr[j]);
flag = true;
}
if (flag) {
count++;
}
}
System.out.println(count);
}
}2차 시도
음수를 고려해야 한다는 사실을 깨닫고 나서 다음으로 한 생각은, i번째 수를 좋은 수로 만드는 경우는 크게 세 가지가 존재한다는 것이었다.
1. i번째 수보다 왼쪽에 있는 두 수를 더해서 i번째 수를 만드는 경우
-> 왼쪽에 있는 두 수가 i번째 수보다 작을 때 성립하므로 i번째 수가 0 이상인 경우이다.
2. i번째 수보다 오른쪽에 있는 두 수를 더해서 i번째 수를 만드는 경우
-> 오른쪽에 있는 두 수가 i번째 수보다 클 때 성립하므로 i번째 수가 0 이하인 경우이다.
3. i번째 수보다 왼쪽에 있는 수 하나, 오른쪽에 있는 수 하나를 더해서 i번째 수를 만드는 경우
예) 정렬된 입력이 -5 3 8일 때 -5와 8을 더해 3을 만드는 경우.
-> 왼쪽에서 선택한 수는 음수, 오른쪽에서 선택한 수는 양수여야 한다. 이 경우는 i번째 수의 부호와 상관 없이 가능하다.
그래서 i의 값에 따라 탐색의 범위를 달리해보면 i번째 수의 부호와 상관 없이 탐색의 범위를 제한해 효율적으로 탐색할 수 있지 않을까? 생각했다.
그래서 다음과 같이 구현해 보았다.
import java.io.*;
import java.util.*;
class Main {
static int[] arr;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
arr = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
if (N < 3) {
System.out.println(0);
return;
}
Arrays.sort(arr);
int count = 0;
for (int i = 0; i < N; i++) {
if (negativePlusPositive(i)) {
count++;
continue;
}
if (arr[i] > 0 && positivePlusPositive(i)) {
count++;
continue;
}
if (arr[i] < 0 && negativePlusNegative(i)) {
count++;
continue;
}
if (arr[i] == 0 && (negativePlusNegative(i) || positivePlusPositive(i))) {
count++;
}
}
System.out.println(count);
}
private static boolean positivePlusPositive(int target) {
for (int i = 0, j = target - 1; i < j;) {
if (arr[i] < 0) {
i++;
continue;
}
if (arr[i] + arr[j] == arr[target]) {
return true;
}
if (arr[i] + arr[j] < arr[target]) {
i++;
} else {
j--;
}
}
return false;
}
private static boolean negativePlusNegative(int target) {
for (int i = target + 1, j = arr.length - 1; i < j;) {
if (arr[j] > 0) {
j--;
continue;
}
if (arr[i] + arr[j] == arr[target]) {
return true;
}
if (arr[i] + arr[j] < arr[target]) {
i++;
} else {
j--;
}
}
return false;
}
private static boolean negativePlusPositive(int target) {
for (int i = 0, j = arr.length - 1; arr[i] <= 0 && arr[j] >= 0 && i < target && target < j;) {
if (arr[i] + arr[j] == arr[target]) {
return true;
}
if (arr[i] + arr[j] < arr[target]) {
i++;
} else {
j--;
}
}
return false;
}
}
이렇게 해서 성공하긴 했지만, 생각보다 빠르지 않았다.
가장 큰 이유는 처음에 i번째 수의 왼쪽, i번째 수의 오른쪽에서 각각 숫자 하나씩을 선택하기 위해 negativePlusPositive()가 이미 i번째 수의 왼쪽, 오른쪽을 탐색하는데 positivePlusPositive()와 negativePlusNegative()도 각각 i번째 수의 왼쪽, 오른쪽을 탐색하는 메소드이기 때문에 탐색이 중복해서 발생하기 때문인 것 같다.
그리고 탐색의 경계를 명확하게 설정할 수 있었다면 굳이 시작 인덱스를 넓게 잡지 않아도 됐을 텐데, 음수도 양수도 아닌 0의 존재가 생각보다 처리하기 곤란했고 같은 수가 여러 번 등장할 수 있기 때문에 i번째 수 이전!! 이후!! 이렇게 딱 나눠지지 않는 상황도 있어 탐색을 중복해서 하지 않을 수가 없었다.
예를 들어 입력이 -1 -1 0이고 두 번째 -1이 좋은 수인지 여부를 확인하는 상황이라고 생각해보자. 내 가정대로라면 -1이 음수이기 때문에 -1의 오른쪽만 탐색을 하면 될 것 같지만 사실 왼쪽에 -1이 또 있기 때문에 왼쪽과 오른쪽을 모두 탐색해야 -1+0=-1이라는 결과를 얻을 수 있다. 탐색을 두 번 해야 하는 것.
최종 구현
그래서 결국에는 그냥 왼쪽 포인터는 0, 오른쪽 포인터는 N-1에서부터 시작해서 최악의 경우 배열 전체를 탐색하는 상황이 오히려 더 시간 복잡도가 낮다는 결론이 나왔다. 적어도 이 경우에는 한 번 선형으로 쭉 탐색을 하면 중복 탐색은 일어나지 않으니까.
두 포인터의 값을 더했을 때 i번째 수보다 크다면 값을 감소시켜야 하기에 오른쪽 포인터 값을 감소시키고, i번째 수보다 작다면 값을 증가시켜야 하기에 왼쪽 포인터 값을 증가시켰다.
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] arr = new int[N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int count = 0;
for (int i = 0; i < N; i++) {
int left = 0;
int right = N - 1;
while (true) {
if (left == i) {
left++;
}
if (right == i) {
right--;
}
if (left >= right) {
break;
}
if (arr[left] + arr[right] < arr[i]) {
left++;
} else if (arr[left] + arr[right] > arr[i]) {
right--;
} else {
count++;
break;
}
}
}
System.out.println(count);
}
}
