https://www.acmicpc.net/problem/2467
*for문을 사용하고 그 안에서 이진탐색*
→ 모든 가능한 용액 쌍을 확인
: for 루프는 용액 배열의 모든 요소에 대해 한 번씩 반복!
각 반복에서는 현재 용액과 나머지 용액 사이의 합을 계산하기 위해 이진 탐색을 사용
따라서 모든 가능한 용액 쌍을 확인가능!
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));
int n = Integer.parseInt(br.readLine());
int[] value = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
value[i] = Integer.parseInt(st.nextToken());
}
int lowValue = 0;
int highValue = 0;
long prevSum = Long.MAX_VALUE;
for (int i = 0; i < n-1; i++) {
int low = i + 1;
int high = n - 1;
while (low <= high) {
int mid = (low + high) / 2;
long sum = value[i] + value[mid];
if (Math.abs(sum) < prevSum) {
lowValue = value[i];
highValue = value[mid];
prevSum = Math.abs(sum);
}
if (sum < 0) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
System.out.println(lowValue + " " + highValue);
}
}
주의할 점
1. sum의 자료형을 int가 아닌 long으로 해야 오버플로우가 발생하지 않았음
2. for문에서 i< n-1로 설정한것
- 인덱스 범위 초과 방지: for 루프의 목적은 각 용액 쌍의 합을 계산하는 것입니다. 용액 쌍의 인덱스는 연속적으로 증가하므로 루프의 반복 횟수를 줄이기 위해 마지막 용액에 대한 루프를 실행하지 않는 것입니다. n-1의 이유는 마지막 용액과 더 이상 쌍을 이루지 않기 때문입니다.
- 이진 탐색 범위 설정: 내부의 이진 탐색 루프에서는 용액 배열의 부분 집합을 대상으로 하고 있습니다. 각 용액은 이미 선택된 용액들과의 합으로 검색됩니다. 따라서 마지막 용액은 다음으로 선택되는 용액과 함께 사용될 수 없으므로 마지막 용액을 고려할 필요가 없습니다.
