[백준/Java] 2470: 두 용액

https://www.acmicpc.net/problem/2470

 

---

 

문제

연구소에 많은 종류의 산성 용액과 알칼리성 용액이 있음

각 용액에는 그 용액의 특성을 나타내는 정수가 주어짐

• 산성: 1부터 1,000,000,000의 양의 정수
• 알칼리성: -1부터 -1,000,000,000까지의 음의 정수

이제 두 용액을 혼합해서 특성값이 0에 가장 가까운 용액을 만들 거임

주어진 용액들의 특성값이 [-2, 4, -99, -1, 98] 인 경우 특성값이 -99인 용액 + 98인 용액 = 특성값이 -1인 용액을 만들 수 있음

이 용액이 특성값이 0에 가장 가까운 용액

 

주어진 용액의 특성값 중 두 개의 서로 다른 용액을 혼합했을 때, 그 값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾아야 함

 

제한사항

• 2 <= 전체 용액의 수 N <= 100,000
• - 1,000,000,000  <= 각 용액의 각 특성값 <= 1,000,000,000
• N개의 용액들의 특성값은 모두 다름
• 산성 용액만 주어지거나 알칼리성 용액만 주어지는 경우도 있음

 

---

 

풀이

투 포인터 활용 문제

 

1. 입력 받은 정수들을 하나의 배열에 저장하여 오름차순 정렬

• 배열의 맨 앞에 있는 수는 강한 알칼리성, 맨 뒤에 있는 수는 강한 산성을 나타냄

 

2. 두 포인터 설정

• 왼쪽 포인터 start는 맨 처음 (가장 작은 값, 가장 강한 알칼리성)
• 오른쪽 포인터 end는 맨 끝 (가장 큰 값, 가장 강한 산성)

 

3. 합 계산 & 포인터 이동

• 현재 위치하고 있는 두 용액의 합 계산
  • 매 계산마다 절댓값이 가장 작은 합과 그 두 용액을 기록
• 합이 0보다 큰 경우 => 합을 작게 만들어야 0에 가까워짐, end--;
• 합이 0보다 작은 경우 => 합을 크게 만들어야 0에 가까워짐, start++;
• 합이 0인 경우 => 이 때의 두 용액이 답, 탐색 중지

 

주의

• start < end 인 상황에만 반복 (서로 다른 용액만 조합해야 하므로)

 

코드

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));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int[] solution = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            solution[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(solution);  // 정렬 (알칼리성 <--> 산성)

        int start = 0;
        int end = solution.length - 1;

        // 두 용액의 합을 구할 때마다 지금까지 구한 합의 최소값을 구하고 그 두 용액도 같이 기록
        int minSum = 2_000_000_000;
        int sol1 = start, sol2 = end;

        while (start < end) {
            int sum = solution[start] + solution[end];
            
            // 최소값 갱신
            if (Math.abs(sum) < Math.abs(minSum)) {
                minSum = sum;
                sol1 = start;
                sol2 = end;
            }

            if (sum > 0) {
                // 두 용액의 합이 0보다 큰 경우 산성이 강하다는 것
                // 따라서 오른쪽에 있는 포인터를 앞으로 이동
                end--;
            } else if (sum < 0) {
                // 두 용액의 합이 0보다 작은 경우 알칼리성이 강하다는 것
                // 따라서 왼쪽에 있는 포인터를 앞으로 이동
                start++;
            } else {
                // 두 용액의 합이 0과 같은 경우
                break;
            }
        }

        sb.append(solution[sol1]).append(' ').append(solution[sol2]);
        System.out.println(sb);
    }

}