[Algorithm] 99클럽 코테 스터디 5일차 TIL BOJ 2470

문제

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

풀이

문제 분석

• 1초는 약 10^8번의 연산을 수행할 수 있다
• 따라서 입력의 크기가 100,000인 경우, 최적의 시간복잡도는 O(NlogN)이하가 되어야 한다
• 또한 두 용액의 합이 0에 가장 가까운 경우의 수를 출력해야 한다고하여 다음과 같은 풀이를 세워보았다

1. 입력을 받는다
2. 정렬을 통해 오름차순으로 주어진 용액들을 정렬한다
3. 투포인터를 통해 용액의 합이 가장 0에 가까운 경우를 찾는다
 - 0이 되는 순간에는 바로 탐색을 멈춘다
 - 두 용액의 합이 음수라면 startIndex를 증가한다
 - 두 용액의 합이 양수라면 endIndex를 감소한다
 - 만약, 이전에 저장된 가장 0에 가까운 수 보다 작은 수가 도출된다면 그 수를 만들 수 있는 경우를 result 1, 2에 각각 저장해준다
4. 탐색이 끝난 후 정답을 출력한다

코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine()); // N개의 용액
        long[] solution = new long[N];
        String[] token = br.readLine().split(" ");

        for(int i = 0; i < solution.length ; i++) {
            solution[i] = Long.parseLong(token[i]);
        }
        Arrays.sort(solution);

        int start = 0;
        int end = N-1;
        int result1 = 0;
        int result2 = 0;
        long compare = 2000000000;

        while(start<end) {
            long temp = solution[start] + solution[end];
            if(temp == 0) {
                result1 = start;
                result2 = end;
                break;
            } else if(temp < 0) {
                if (Math.abs(temp) < compare) {
                    result1 = start;
                    result2 = end;
                    compare = Math.abs(temp);
                }
                start++;
            }
            else {
                if(Math.abs(temp) < compare) {
                    result1 = start;
                    result2 = end;
                    compare = Math.abs(temp);
                }
                end--;
            }
        }

        bw.write(solution[result1] + " " + solution[result2]);
        bw.flush();
        bw.close();
    }
}

TIL

투포인터 알고리즘을 사용할 경우에 대해서는 시간 복잡도가 O(N)이 소요된다
그러나 내가 푼 방식은 정렬이 되어있다는 가정하에 사용할 수 있으므로 정렬 시간을 포함하여 O(NlogN)의 시간복잡도가 소요된다

문제를 푼 이후 항해99의 힌트를 보니 이분탐색으로 풀 수 있다고 나와있었다
아마 이 힌트를 보았다면 이분탐색으로만 풀어야겠다는 생각에 빠르게 문제를 해결하지 못했을 수도 있을 것 같다

그러나 학습을 위해 이분 탐색으로도 푸는 방법을 찾아보았다

그 풀이는 다음과 같다

1. 입력을 받는다
2. 정렬을 통해 오름차순으로 주어진 용액들을 정렬한다
3. 인덱스 0부터 하니씩 꺼내어 해당 인덱스에 해당하는 수(A)에 -를 붙여 해당 값보다 크거나 같은 첫 번째 인덱스를 반환한다(lower bound)
  - 이렇게 찾은 인덱스에 해당하는 값(B)가 -A와 동일한 값이 아니고, 두 수의 합(A+B)의 절대값이 최소(0에 가까우면) 갱신한다
  - LowerBound를 통해 찾은 인덱스 -1도 고려하여 값을 갱신해야 한다

위 풀이에서 LowerBound를 통해 찾은 인덱스 -1도 고려하여 값을 갱신해야 하는 이유는 다음과 같다

ex) -10 -5 4 7
현재 검사하는 인덱스가 1이여서 A가 -5라고 할 때 lower bound를 통해 B를 구하면 B는 7이 된다
그러나 실제로는 -5 + 4 = 1이 0에 더 가까운 숫자이므로 lower bound-1의 인덱스도 확인해야 하는 것이다

해당 풀이에 대한 코드는 다음과 같다

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine()); // N개의 용액
        long[] solution = new long[N];
        String[] token = br.readLine().split(" ");

        for(int i = 0; i < solution.length ; i++) {
            solution[i] = Long.parseLong(token[i]);
        }
        Arrays.sort(solution);

        int result1 = 0;
        int result2 = 0;
        long compare = 2000000000;

        for(int i = 0; i < N-1 ; i++) {
            int start = i + 1;
            int end = N-1;
            long target = -solution[i];
            int found = lowerBound(solution, start, end, target);

            if (found < N && Math.abs(solution[i] + solution[found]) < compare) {
                compare = Math.abs(solution[i] + solution[found]);
                result1 = i;
                result2 = found;
            }
            if (found - 1 > i && found - 1 < N && Math.abs(solution[i] + solution[found - 1]) < compare) {
                compare = Math.abs(solution[i] + solution[found - 1]);
                result1 = i;
                result2 = found - 1;
            }
        }

        bw.write(solution[result1] + " " + solution[result2]);
        bw.flush();
        bw.close();
    }

    public static int lowerBound(long[] arr, int start, int end, long target) {
        while(start < end) {
            int mid = (start + end) / 2;
            if(arr[mid] == target) {
                return mid;
            }
            if(arr[mid] < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }
}

풀이 과정을 알고 난 후 직접 코드를 적으면서 문제를 통과하지 못했었는데, upper bound로 찾은 index의 값의 범위를 검사해야 한다는 점이었다

검사하지 않는 경우에는 index out of bound 에러를 마주치게 된다 :-)....