[알고리즘 문제] 두 용액

import java.util.*;

public class Main {

    // static ArrayList<Integer> copy = new ArrayList<Integer>();
    static ArrayList<Integer> list = new ArrayList<Integer>();
    static ArrayList<Integer> plus = new ArrayList<Integer>();
    static ArrayList<Integer> minus = new ArrayList<Integer>();

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int num;
        for (int i = 0; i < n; i++) {
            num = sc.nextInt();
            if (num < 0) {
                minus.add(num);
            } else {
                plus.add(num);
            }
            list.add(num);
        }

        Collections.sort(list);
        Collections.sort(plus);
        Collections.sort(minus);

        int result = 0;

        int min = 987654321;
        int big = 0, small = 0, gap = 0;
        int n1 = 987654321, n2 = 0;

        for (int j = 0; j < n; j++) { // O(n)

            num = list.get(j);
            // copy.addAll(list);
            // copy.remove(j); // O(n)

            result = search(num);

            // copy.clear(); /// O(n)

            if (num > result) {
                big = num;
                small = result;
            } else {
                big = result;
                small = num;
            }

            gap = Math.abs(num + result);

            if (gap <= min) {
                if (small < 0 && n1 < 0 && small > n1) {
                    n1 = small;
                    n2 = big;
                    min = gap;
                    continue;
                }
                if (small < n1) {
                    n1 = small;
                    n2 = big;
                    min = gap;
                }
            }
        }
        System.out.println(n1 + " " + n2);
    }

    static int search(int num) { // num과 더해서 0이되거나, 0에 가장 가까운 값을 구하는 함수

        int n;
        int start, end;
        int min;

        if (num < 0) {
            n = Math.abs(num);
        } else {
            n = 0 - num;
        }

        start = 0;
        end = list.size() - 1;

        if (minus.size() == 0) { // 숫자가 양수만 있는 경우
            if (num == list.get(start)) {
                return list.get(start + 1);
            } else if (num == list.get(end)) {
                return list.get(start);
            } else {
                return list.get(start);
            }
        } else if (plus.size() == 0) { // 숫자가 음수만 있는 경우
            if (num == list.get(start)) {
                return list.get(end);
            } else if (num == list.get(end)) {
                return list.get(start);
            } else {
                return list.get(end);
            }
        }
        if (list.get(start) == n) { // num과 정확히 반대되는 값을 찾으면 그 값을 return
            return list.get(start);
        } else if (list.get(end) == n) {
            return list.get(end);
        }

        if (num < 0) {

            if (list.get(end) < n) {
                return list.get(end);
            }
        } else {
            if (list.get(start) > n) {
                return list.get(start);
            }
        }

        int mid;

        while (start + 1 < end) {
            mid = (start + end) / 2;

            if (list.get(mid) == n) {
                return list.get(mid);
            }

            if (list.get(mid) > n) {
                end = mid;
            } else if (list.get(mid) < n) {
                start = mid;
            }
        }
        if (list.get(start) == num) {
            return list.get(end);
        } else if (list.get(end) == num) {
            return list.get(start);
        }
        if (Math.abs(num + list.get(start)) < Math.abs(num + list.get(end))) {
            min = list.get(start);
        } else {
            min = list.get(end);
        }
        return min;
    }
}

 

이 문제 자체는 이해하기 쉽다. 여러개의 정수들이 입력되고 이 정수에서 양수를 산성, 음수는 알카리 용액으로 표현한다.

여기서 산성과 알카리 용액을 더했을 때, 0에 가장 가까까운 두 용액을 구하는 문제이다. 추가적으로 용액이 산성으로만 이루어져 있거나 알카리로만 이루어져 있는 경우도 있다.

 

아이디어는 먼저 입력받은 정수들을 정렬하고, 각 정수마다 해당 정수값의 반대값을 이진탐색으로 구한다. 여기서 이 반대값을 구하는 로직은 search함수가 수행하고 인자로 정수를 입력받는다.

 

search함수 내부에서는 start와 end,mid라는 변수를 사용하여 이진탐색을 한다. start는 찾으려는 정수 num보다 항상 작은 값이거나 가장 멀리 있는 값의 인덱스, end는 찾으려는 정수 num보다 항상 큰 값이거나 가장 가까운 값의 인덱스, mid는 start와 mid의 가운데 값이다. 이진 탐색을 하기 전에, 만약 start와 end위치에 찾으려는 정수가 있다면 그 값을 바로 return해준다. 그렇지 않다면 이제 이진탐색을 시작한다.

 

** 여기서 start와 end의 조건을 만족하지 못하는 부분은 search함수에서 while문 시작 전 if문에서 모두 걸러주게 된다.

 

-2 4 -99 1 98라는 숫자를 입력 받았고, 이 숫자를 정렬하면 -99 -2 1 4 98이 된다. -99를 기준으로 더했을 때, 0과 가장 가깝게 만드는 정수를 찾아보자.

 

-99 -2 1 4 98    start=0 , end = 4 mid=2   -> 2번째 인덱스 값은 1이므로 99보다 작다. 그러므로 start=mid가 된다.

-99 -2 1 4 98    start=2 , end = 4 mid=3   -> 3번째 인덱스 값은 4이므로 99보다 작다. 그러므로 start=mid가 된다.

-99 -2 1 4 98    start=3 , end = 4 mid=?   -> while문 조건이 start+1 < end이므로 최종 값은 start는 3, end=4가 된다.

 

여기까지 오게 된다면 -99와 반대 값, 즉 99를 찾지 못했다. 그렇다면 여기서 start와 end값을 비교해준다. 하지만, 비교해주기 전에 start와 end번째 값이 99와 같은지 아닌지 먼저 검사를 해준다. 만약 start번째의 값과 99가 같게 되면 end값을 return 해준다.

 

둘 중 하나라도 같은 값이 없게되면 -99와 start번째 값, end번째 값을 각각 더해서 절대값이 작은 값을 return 해준다.

이렇게 되면 입력받은 하나의 정수에 대해 더했을 때, 0이거나 0에 가장 가까운 값을 구할 수 있다.

 

이렇게 두 용액을 구하고, 두 용액을 더했을 때의 절대값을 구해준다. 만약 절대값이 기존의 최저절대값보다 작게 되면 기존의 최저 절대값을 수정해주고 동시에 만약 두 용액중에서 작은값이 기존의 용액의 최저값보다 작다면 현재 용액을 최종 출력값 변수에 저장해주게 된다.

 

----------------------------------------------------------------------------------------------------------------------------

이 문제를 처음 풀었을 때, 몇몇 테스트케이스가 시간초과가 나왔다. 문제는 주석으로 처리된 부분, 기존의 리스트를 복사하고 복사된 리스트에서 내가 찾으려는 숫자를 지워주고, 탐색이 끝났을 때 다시 리스트를 초기화 해주는 작업을 했었는데 이 부분에서 시간이 오래 걸렸다.

 

ArrayList의 remove와 clear메서드가 O(n)의 추가적인 시간이 걸렸기 때문이다. 이 부분은 부가적인 list를 만들어서 처리해주기 보다는 check함수에서 if문을 추가 함으로써 해결했다.