백준 2467번 [용액](C++) -yes6686- 티스토리

백준 문제 풀이: 2467 [용액]

---

문제 링크: https://www.acmicpc.net/problem/2467

문제 설명:

n개의 용액이 주어졌을 때, 두 용액을 혼합하여 그 특성값(합)의 절댓값이 0에 가장 가까운 두 용액을 찾는 문제입니다. 용액은 음수, 0, 양수로 구성되며, 두 용액을 혼합했을 때의 특성값은 두 용액의 합으로 정의됩니다.

• 용액의 수 n은 최대 100,000개입니다.
• 두 용액의 특성값이 0에 가까운 조합을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int arr[100001];

bool compare(int a, int b) {
    return abs(a) < abs(b);
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr, arr + n, compare);

    int result1 = 0;
    int result2 = 0;
    int min = 2e9;

    for (int i = 1; i < n; i++) {
        if (min > abs(arr[i - 1] + arr[i])) {
            min = abs(arr[i - 1] + arr[i]);
            if (arr[i - 1] > arr[i]) {
                result1 = arr[i];
                result2 = arr[i - 1];
            } else {
                result1 = arr[i - 1];
                result2 = arr[i];
            }
        }
    }
    cout << result1 << ' ' << result2;
}

예제

입력:
5
-2 4 -99 -1 98

출력:
-99 98

---

코드 설명

• 입력 및 정렬:
  • 입력받은 배열을 특성값의 절댓값 기준으로 오름차순 정렬합니다. 이는 가장 작은 특성값의 조합을 효율적으로 탐색하기 위함입니다.
• 최소 특성값 탐색:
  • 정렬된 배열을 순회하며 인접한 두 값의 합의 절댓값을 계산합니다.
  • 현재 계산한 절댓값이 기존 최솟값보다 작으면, 해당 두 값을 결과로 갱신합니다.
• 출력: 두 용액을 오름차순으로 출력합니다.

시간 복잡도

• 정렬: O(n log n)
• 탐색: O(n)
• 총 시간 복잡도: O(n log n)

---

결과

이 코드는 입력된 용액 배열에서 가장 특성값이 0에 가까운 두 용액을 정확히 탐색합니다. 정렬 및 단순 탐색으로 효율적으로 동작합니다.