백준 2470번 <두 용액>

백준 알고리즘 2470번

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

2470번: 두 용액

---

2470번

많은 종류의 산성 용액과 알칼리성 용액이 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

---

문제 해결

투포인터를 이용해 문제를 풀었다.

 

입력으로 들어오는 용액 특성값들을 오름차순으로 정렬하고 투포인터를 진행한다.

 

start를 0부터 N-2까지 증가시켜가며 진행하고 end를 N-1부터 감소시켜가며 number[start] + number[end] >= 0일 때, start를 기준으로 end의 최댓값을 구한다.

end의 값은 감소시키기 때문에 end가 작아지면 필연적으로 number[start] + number[end]의 값은 작아진다.

 

start와 end가 될 수 있는 경우의 수는 다음과 같다.

• start와 end 모두 음수인 경우
  • 0과 가장 가까워야 하기 때문에 N-1번째와 N-2번째를 더한 값이 정답이 된다. 즉, end는 그대로고, start가 N-2까지 증가되어야 한다.
• start와 end 모두 양수인 경우
  • 0과 가장 가까워야 하기 때문에 0번째와 1번째를 더한 값이 정답이 된다. 즉, start 는 그대로고, end 가 1까지 감소되어야 한다.
• start는 음수, end는 양수인 경우
  • number[start] + number[end]의 값이 0보다 크다면 end를 감소시켜가며 최대 end의 값을 구한다.
  • number[start] + number[end]의 값이 0보다 작거나 같다면 number[start]의 값이 음수라는 의미이고 end의 값을 감소시키면 절댓값이 0보다 커지기 때문에 더 이상 볼 필요가 없다.

---

코드

import java.awt.event.WindowAdapter;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ_2470 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String[] inArr = br.readLine().split(" ");
        int[] number = new int[N];
        for (int i = 0; i < N; i++) {
            number[i] = Integer.parseInt(inArr[i]);
        }
        // end input

        Arrays.sort(number);
        int end = N - 1;
        int acc = Integer.MAX_VALUE;
        int[] answer = {0, 0};
        for (int start = 0; start < N - 1; start++) {
            int temp = Math.abs(number[start] + number[end]);
            if (start < end) {
                if (acc > temp) {
                    acc = temp;
                    answer[0] = number[start];
                    answer[1] = number[end];
                }
            }
            while (start < end - 1 && number[start] + number[end] > 0) {
                end--;
                temp = Math.abs(number[start] + number[end]);
                if (acc > temp) {
                    acc = temp;
                    answer[0] = number[start];
                    answer[1] = number[end];
                }
            }
        }
        System.out.println(answer[0] + " " + answer[1]);
    }
}

---

결과

---