[백준OJ] 14921번 용액 합성하기

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

14921번: 용액 합성하기

---

 

-풀이-

오름차순으로 정렬한 뒤(문제에서 정렬된 상태로 입력된다했으므로 생략) , 투포인터를 이용하여 두개의 포인터가 겹치기 전까지, 두 포인터가 가리키고 있는 용액값의 합의 절댓값이 작으면 갱신한 뒤, 용액의 값을 저장해둔다.

그런 뒤, 합이 음수면 left포인터를 ++, 합이 양수면 right포인터를 -- 해주면서 합이 0과 가까워 지도록 만들어주며 절댓값의 최솟값을 갱신시켜주면된다.

 

-시간복잡도-

오름차순 정렬을 안해주어도 되므로, O(N)이 된다.

 

-코드-

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

int n;
int arr[100010];

int main(){
    cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }

    int left=0;
    int right=n-1;
    int min=987654321;
    int result=-1;
    while(left<right){
        int s=arr[right]+arr[left];
        if(abs(s)<min){
            min=abs(s);
            result=s;
        }
        
       if(s>0){
           right--;
       }
       else{
           left++;
       }
    }
    cout<<result;
}