[Jungol] 정올 2306 두 용액

출처: [Jungol] 2306 두 용액

 Input 

5

-2 4 -99 -1 98

 

 Output 

-99 98

같은 문제 다른 풀이: [BOJ] 2470 두 용액 

[BOJ] 백준 2470 두 용액

 

① 실제로 채점되는 Input Data는 정렬되어 있지 않기 때문에 주어진 숫자 정렬

    ex) {-2 4 -99 -1 98} → {-99 -2 -1 4 98}

② 두 개의 인덱스 low, high를 이용합니다.

    low = 0, high = N-1 ← 초기값: 배열의 양쪽 끝 인덱스

③ sum = arr[low] + arr[high];결과에 따른 분기

ex) [-9  -8  -3  -1  0  2  5  12]

▶ sum > 0이 되면 high--; / sum < 0이 되면 low++;

▷ -9 + 12 = 3 > 0 이므로 high--

    왜냐하면 정렬된 배열에서 12가 가장 큰 수인데 더 큰 양수를 찾아서 『0』과 멀어질 필요가 없기 때문입니다.

▷ -9 + 5 = -4 < 0 이므로 low++

    여기서도 만약 high를 감소해서 -9 + 2 = -7이 되어 『0』과 더 멀어지므로  low++하여 『0』과 가까워 질 수 있습니다

    현재 범위에서 가장 큰 값과 더한 결과가 음수(-)이므로,

    이것보다 low에 가까운 값들과 더해봤자 음수 방향으로 『0』에서 부터 멀어질 뿐이다.

▷ -8 + 5 = -3 < 0 이므로 low++

▷ -3 + 5 = 2 > 0 이므로 high--

▷ -3 + 2 = -1 < 0 이므로 low++

▷ -1 + 2 = 1 > 0 이므로 high--

▷ -1 + 0 = -1 < 0 이므로 low++

→ low == high이므로 탐색 종료 혹은 탐색 중간에 두 수의 합 = 0이 되는 경우가 있으면 종료해도 됩니다.

 

 

[-100 -45 -7 7 46 100]

만약 arr[low] + arr[high] = -100 + 100 = 0 인 경우에는 추가 탐색할 필요가 없습니다.

왜냐하면 0에 가장 가까운 두 수를 찾는 것인데, 두 수의 합 = 0이면 더이상 탐색할 필요가 없기 때문입니다.

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
typedef long long ll;
const int LM = 100001;
const int INF = (int)21e8;
int N, x, y, ans = INF;
int arr[LM], copyArr[LM];
inline int abs(int A) { return  A < 0 ? -A : A; }
 
// 합병 정렬
void mergeSort(int*arr, int s, int e) {
    if (s >= e) return;
 
    int m = (s + e) / 2;
    mergeSort(arr, s, m);
    mergeSort(arr, m + 1, e);
 
    int i = s, j = m + 1, k = s;
    while (i <= m && j <= e) {
        if (arr[i] < arr[j]) copyArr[k++] = arr[i++];
        else copyArr[k++] = arr[j++];
    }
    while (i <= m) copyArr[k++] = arr[i++];
    while (j <= e) copyArr[k++] = arr[j++];
 
    for (i = s; i <= e; ++i) {
        arr[i] = copyArr[i];
    }
}
void process() {
    int low = 0, high = N - 1, sum;
    while (low < high) {
        sum = arr[low] + arr[high];
 
        // 0과 가까운 두 수의 인덱스로 갱신 
        if (ans > abs(sum)) {
            ans = abs(sum);
            x = low;
            y = high;
        }
        if (sum == 0) {
            x = low; y = high;
            return;
        }
        else if (sum > 0) {
            high--;
        }
        else { // sum < 0
            low++;
        }
    }
}
 
int main(void) {
    scanf("%d", &N);
    for (int i = 0; i < N; ++i)
        scanf("%d", &arr[i]);
    
    // 숫자 정렬
    mergeSort(arr, 0, N - 1);
 
    process();
 
    // 인덱스가 아닌 원소값 출력
    printf("%d %d\n", arr[x], arr[y]);
    return 0;
}