<두 포인터> BOJ 2470 두 용액
문제
산성 용액과 알칼리성 용액의 특성값이 배열로 주어질때 두 용액의 특성 값의 합이 0에 가장 가까운 경우를 찾는 문제입니다.(절대값이 작으면 되겠죠?)
- 전체 용액의 수 N <= 100000
접근
- 이중 for문을 사용했다간 100억이라는 숫자를 맞을 테니 이중 for문을 대체할 두 포인터 알고리즘을 떠올린다.
- 두 포인터 알고리즘을 적용하고자 하니 음수가 걸린다.
- 하지만 문제가 합이 가장 크거나 가장 작은걸 고르는게 아닌 0에 가까운 수를 고르는 것이다. 따라서 이런 전략을 생각해본다.
- 3-1. 배열을 정렬한다.
- 3-2. 포인터 두개를 각각 0과 배열 마지막에 둔다.
- 3-3. 두개의 합이 0보다 작다면 왼쪽 포인터를 오른쪽으로 움직인다.
- 3-4. 두개의 합이 0보다 크다면 오른쪽 포인터를 왼쪽으로 움직인다.
3-3, 3-4 두 경우 모두 커지거나 작아질 것이 확실하므로 두 포인터를 사용 가능하다.
- 반대 방향에서 포인터가 출발하므로 에 해결 가능합니다.
코드
import java.io.*;
import java.util.*;
class Pair {
int i;
int j;
int val;
Pair(int i, int j, int val) {
this.i = i;
this.j = j;
this.val = val;
}
}
class baek__2470 {
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];
String[] temp = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(temp[i]);
}
Arrays.sort(arr);
int p1 = 0;
int p2 = arr.length - 1;
Pair pair = new Pair(-1, -1, -1);
int sum = arr[p1] + arr[p2];
pair.i = p1;
pair.j = p2;
pair.val = sum;
while (p1 < p2) {
if (Math.abs(sum) < Math.abs(pair.val)) {
pair.i = p1;
pair.j = p2;
pair.val = sum;
}
if (sum > 0) {
sum -= arr[p2];
p2--;
sum += arr[p2];
} else if (sum == 0) {
break;
} else {
sum -= arr[p1];
p1++;
sum += arr[p1];
}
}
System.out.print(arr[pair.i] + " " + arr[pair.j]);
}
}
Author And Source
이 문제에 관하여(<두 포인터> BOJ 2470 두 용액), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@since-1994/두-포인터-BOJ-2470-두-용액저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)