[알고리즘] 두 용액(백준2470번)_골드5_투포인터

문제링크

📝 문제

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

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

예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

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

입력

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

예제 입력 1

5
-2 4 -99 -1 98

예제 출력 1

-99 98

---

🔍 정답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] solution = new int[N];    // 용액의 특성을 담을 배열
        int[] result = new int[2];      // 결과값을 담을 배열
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 입력 받기
        for (int i = 0; i < N; i++) {
            solution[i] = Integer.parseInt(st.nextToken());
        }

        // 오름차순 정렬!
        Arrays.sort(solution);

        // 양 끝의 인덱스부터 비교하기 위함
        int i = 0;
        int j = solution.length - 1;

        /**
         * 양 끝 인덱스를 더했을 때,
         * 0보다 크다면 크기가 큰 j 인덱스를 줄이고 0보다 작다면 i인덱스를 늘린다.
         * 그리고 더한 값의 절대값이 작을 수록 0에 가까운 것이므로 min과 비교해서 갱신해준다.
         */
        int min = Integer.MAX_VALUE;
        while (i < j) {
            int sum = 0;
            int temp = 0;

            sum = solution[i] + solution[j];
            temp = Math.abs(sum);
            if (min > temp) {
                min = temp;
                result[0] = solution[i];
                result[1] = solution[j];
            }

            if (sum > 0) j--;
            else i++;
        }

        System.out.println(result[0] + " " + result[1]);
    }
}

• 투포인터 알고리즘을 이용해서 시간복잡도를 O(N)으로 줄여야 하는 문제였다.
• 핵심은 정렬이었는데,
• 음수와 양수가 섞인 배열이라면 가운데로 갈 수록 절댓값이 작아질 것이다.
  • {-2 4 -99 -1 98} -> {-99 -2 -1 4 98}
  • -1의 절댓값이 0에 가장 가깝다.
• 백트래킹의 경우 -99가 -2와 -1, 4, 98을 한 번씩 다 더해보면서 0에 가까운 수를 찾게 되는데, 정렬을 하고 양 끝을 더했을 때 결과값이 0보다 작다면 -2, -1은 계산할 필요가 없다. 왜냐하면 계산해봤자 0과 더 멀어지기 때문이다. 그래서 -2로 인덱스 이동을 하고 다시 탐색을 하게 되는 것이다.
• 만약 모두 양수로 된 배열이라면 sum값이 계속해서 0보다 클 것이기 때문에 오른쪽 인덱스를 계속 줄이며 결국 가장 작은 값 2개를 선택하게 될 것이다.

2023.02.18 - [알고리즘] - [알고리즘] 투포인터(Two pointers)

 

❌ 오답(처음풀이, 백트래킹)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int[] solution;
    static boolean[] visit;
    static int[] calc;
    static int[] result;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        solution = new int[N];
        visit = new boolean[N];
        calc = new int[2];
        result = new int[2];
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        dfs(0, 0);
        System.out.println(result[0] + " " + result[1]);
    }

    public static void dfs(int num, int depth) {
        if (depth == 2) {
            int sum = 0;
            sum = calc[0] + calc[1];

            if (min > Math.abs(sum)) {
                min = Math.abs(sum);

                if (calc[0] > calc[1]) {
                    result[0] = calc[1];
                    result[1] = calc[0];
                } else {
                    result[0] = calc[0];
                    result[1] = calc[1];
                }
            }
            return;
        }

        for (int i = num; i < N; i++) {
            if (!visit[i]) {
                visit[i] = true;
                calc[depth] = solution[i];
                dfs(i, depth+1);
                visit[i] = false;
            }
        }
    }
}

• 백트래킹 방식으로 완전 탐색을 하게 되면 시간 초과가 나온다 ㅠㅠ