(C++, Python3) - 백준(BOJ) 2470번 : 두 용액 답

www.acmicpc.net/problem/2470

2470번: 두 용액

Binary Search 혹은 Two Pointer로 풀 수 있던 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

배열길이와 배열을 입력받고 오름차순으로 원소들을 저장합니다.

📔 풀이과정

📑 Two Pointer
 1. 두 용액의 특성값을 더했을때 기존에 있던 결과값보다 작다면 갱신

 2. 두 용액의 특성값 합이 0이하면 left pivot을 ++

 3. 두 용액의 특성값 합이 0초과면 right pivot을 --

 4. 최종 결과값 출력

시간 복잡도 : O(N)

공감 복잡도: O(N)

 

📑 Binary Search

• 오름차순 정렬
  • 두 용액을 선택할 것이므로, O(N log N)로 정렬 후 적절한 원소를 빠르게 찾을 수 있습니다.
• 각 원소 a[i]에 대해, x = -a[i]와 가장 가까운 값을 찾기
  • bisect.bisect_left()를 사용하여 -a[i]와 가장 가까운 값을 찾습니다. → O(log N)
  • 이는 c++ 의 lower_bound()와 비슷한 동작을 합니다.
  • 찾은 값이 a[i] 자신이라면, 다른 원소를 선택해야 합니다.
• 두 원소의 합이 0에 가장 가까운 쌍을 갱신
  • abs(a[i] + a[j]) < abs(diff)이면 num1, num2 갱신해줍니다.
• 최종적으로 오름차순 출력
  • 두 수를 sorted()하여 출력합니다.
• 시간 복잡도: O(Nlog(N))

📔 정답 출력 | 반환

오름차순으로 두 수를 출력합니다.

---

📕 Code

📔 C++

#include <iostream> 
#include <algorithm> 
#include <cmath> 
#include <vector> 
using namespace std; 
vector <int> liquid; 
int n; 
void twoPointer(int n){ 
    int left = 0; 
    int right = n-1; 
    int rightValue, leftValue, sum = 0; 
    int result = 0x7f7f7f7f; 
    while(left<right){ 
        sum = (liquid[left] + liquid[right]); 
        if(abs(result) > abs(sum)){ 
            result = sum; 
            leftValue = liquid[left]; 
            rightValue = liquid[right]; 
        } 
        if(sum <= 0) left++; 
        else right--; 
    } 
    cout << leftValue << ' ' << rightValue <<'\n'; 
} 
int main(){ 
    cin >> n; 
    for(int i = 0; i <n; i++){ 
        int feature; 
        cin >> feature; 
        liquid.push_back(feature); 
    } 
    sort(liquid.begin(),liquid.end()); 
    twoPointer(n); 
}

📔 Python3

import bisect
import sys
input = sys.stdin.readline

n = int(input())
a = sorted(list(map(int, input().split())))

def binary_search_closest(target, exclude_idx):
    idx = bisect.bisect_left(a, target)
    candidates = []

    if idx < len(a) and idx != exclude_idx:
        candidates.append(a[idx])
    if idx > 0 and idx - 1 != exclude_idx:
        candidates.append(a[idx - 1])

    return min(candidates, key=lambda num: abs(num - target)) if candidates else None

num1, num2, diff = 0, 0, 10**10

for i in range(n):
    x = -a[i]
    y = binary_search_closest(x, i)

    if y is None:
        continue

    if abs(a[i] + y) < abs(diff):
        num1, num2, diff = a[i], y, abs(a[i] + y)

print(*sorted([num1, num2]))

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.