[백준] 2467번 - 용액 c++

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

 

문제 설명

산성 용액과 알칼리성 용액의 특성값이 정렬된 순서로 주어졌을 때,

이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들자.

 

조건

• N은 2 이상 100,000 이하의 정수
• 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하
• 오름차 순으로 주어짐

풀이 방법

고민을 많이 했던 문제이다.

만약 10만 크기의 배열을 선언 뒤 이중 for문으로 찾게 된다면 O(100000*100000) = O(10000000000)

약 100억의 시간복잡도가 걸리기 때문에 매우 비효율적이다. (O(n*2))

 

그러므로 투 포인터 방식을 사용하면 된다.

liquid[100000]  

left = 0

right = n-1 로 선언하여 양 끝 인덱스 위치를 구한다.

 

그다음  liquid[left] + liquid[right]가 0보다 크다면 left++,

0보다 작다면 right--를 해주며 liquid의 합이 0에 가까워질때까지 반복한다.

이 경우 배열을 최대 한번만 순회하므로  O(100000) 즉, O(n)의 시간복잡도가 걸린다.

 

풀이 코드

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int n, liquid[100000], answer[2];
int main() {
    cin >> n;
    for(int i=0; i<n; i++) cin >> liquid[i]; 
    int min_num = 2100000000;
    int left = 0, right = n-1;
    
    while(left < right){
      if(min_num>abs(liquid[left]+liquid[right])){
            min_num = abs(liquid[left]+liquid[right]);
            answer[0] = liquid[left];
            answer[1] = liquid[right];
        } 
        
        if(liquid[left]+liquid[right]<0) left++;
        else if(liquid[left]+liquid[right]>0) right--;
        else break;
    }
    cout << answer[0] <<" "<<answer[1]<<'\n';
    return 0;
}