Backjoon(백준) 2470- 두 용액 (Java)
문제링크
( https://www.acmicpc.net/problem/2470 )
분류
- TwoPointers Algorithm
1. 풀이 힌트
- 주어진 용액들을 오름차순으로 정렬한 뒤, 양쪽 끝에 포인터를 두어 두 용액의 합이 0보다 크면 오른쪽 포인터를 왼쪽으로 한칸, 0보다 작으면 왼쪽 포인터를 오른쪽으로 한칸 옮기면서 두 포인터가 만날때 까지 각각의 합을 구하고, 도출된 합 중에서 0과 가장 가까운 결과에 해당하는 포인터가 지목하는 용액의 값을 오름차순으로 출력하면 된다.
2. 풀이 과정
1) 밑과 같이 각 용액이 주어졌을 때 먼저 오름차순으로 정렬한다
| -2 | 4 | -99 | -1 | 98 |
2) 오름차순으로 정렬된 용액들
| -99 | -2 | -1 | 4 | 98 |
3) 양쪽 끝에 포인터를 둔다
- 왼쪽 끝의 포인터는 파랑색으로 표현, 오른쪽 포인터는 빨간색으로 표현
| -99 | -2 | -1 | 4 | 98 |
4) 각 포인터가 위치한 두 용액의 합을 구한다
- 포인터가 양 끝에 위치하므로 두 용액의 합을 구하면 -1이 나온다(-99 + 98)
5) 포인터에 위치한 두 용액 합의 결과가 마이너스이면 왼쪽(파란색) 포인터를 오른쪽으로 한칸 옮긴다.
- 두 용액의 합이 마이너스가 나왔다는 뜻은 두 용액의 값중 마이너스 용액의 값이 크다는 뜻이므로 좀 더 작은 마이너스를 가진 용액으로 포인터를 옮기기위해 왼쪽 포인터를 오른쪽으로 한칸 옮기는 것이다.
| -99 | -2 | -1 | 4 | 98 |
6) 포인터를 옮겼으면, 두 포인터가 가르키는 두 용액의 합을 구한다
- 결과는 96으로 이번에는 두 용액 합이 플러스가 됐다. 플러스 일때는 오른쪽(빨간색) 포인터를 왼쪽으로 한 칸 옮긴다.
7) 과정 반복
- 두 포인터가 만날 때 까지 위와 같은 과정을 반복하고, 각 과정을 시행하면서 나온 두 용액의 합은 따로 하나의 배열에 저장한다.
8) 배열에 저장된 값중에 0과 가장 가까운 값을 나타내는 두 용액이 정답이된다.
2. 풀이 과정
3. 코드 풀이 (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class TwoSolutions {
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]; // 용액들을 저장할 배열
int[] dp = new int[n - 1]; // 두 용액의 합을 저장할 배열
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) { // 용액 저장
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr); // 오름차순으로 정렬
int pL = 0; // 왼쪽 포인터
int pR = n - 1; // 오른쪽 포인터
int result = arr[pL] + arr[pR]; // 0과 가장 가까운 값을 비교하기 위한 변수 선언
int resultPL = arr[pL]; // 0과 가장 가까운 값을 이루고 있는 용액 1
int resultPR = arr[pR]; // 0과 가장 가까운 값을 이루는 용액 2
for (int i = 0; i < n - 1; i++) {
dp[i] = arr[pL] + arr[pR];
if (Math.abs(dp[i]) < Math.abs(result)) { // 결과값 최신화
result = dp[i];
resultPL = arr[pL];
resultPR = arr[pR];
}
// 두 용액 합의 결과에 따라 포인터 이동
if (dp[i] > 0) {
pR--;
} else if (dp[i] < 0) {
pL++;
} else { // 두 용액의 합이 0이면 for문을 종료
break;
}
}
// 결과 출력
System.out.println(resultPL + " " + resultPR);
}
}