문제
풀이
투 포인터와 이분 탐색을 이용하는 문제이다.
알고리즘은 아래와 같다.
1. left = 0, right = N-1
2. while(left < right):
3. sum = sols[left] + sols[right]
4. if(abs(sum) < min):
5. min = abs(sum)
6. res_left = left, res_right = right //res_left, res_right는 현재까지 가장 0에 가까운 용액을 만들어내는 특성값
7. if(sum > 0): //합이 양수라면 더 작은 sols[right]에 대해 sum이 0에 더 가까워질 가능성 有
8. right --
9. else: //합이 음수일 때도 마찬가지
10. left ++
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
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());
StringTokenizer st=new StringTokenizer(br.readLine());
int[] sols=new int[N];
for(int i=0; i<N; i++) {
sols[i]=Integer.parseInt(st.nextToken());
}
int min=Integer.MAX_VALUE;
int leftRes=0, rightRes=0;
int left=0, right=N-1;
while(left<right) {
int sum=sols[left]+sols[right];
if(min>Math.abs(sum)) {
min=Math.abs(sum);
leftRes=left; rightRes=right;
}
//binary search
if(sum>=0) {
right--;
}
else {
left++;
}
}
System.out.println(sols[leftRes]+" "+sols[rightRes]);
}
}
'백준' 카테고리의 다른 글
백준 17298: 오큰수(java) (0) | 2024.10.13 |
---|---|
백준 2473: 세 용액(java) (0) | 2024.10.11 |
백준 1806: 부분합(java) (0) | 2024.10.08 |
백준 1253: 좋다(java/python) (0) | 2024.10.07 |
백준 1940: 주몽(java/python) (0) | 2024.10.01 |