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);

    }

}