[C/C++ ] 백준 2467: 용액 (두 포인터)

2467: 용액

 

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

2467번: 용액

맨 처음에는 bruteforce하게 문제 접근하여 각 경우마다 안되는 경우를 계산하여 시간복잡도가 O(n^2/4)짜리 알고리즘을 짰지만 시간초과가 나왔다. 그 후 이 문제를 "두 포인터"를 이용해 풀었다. 

 

두 포인터란?

 두 포인터/ 투 포인터는 말 그대로 두 개의 포인터를 이용해 문제를 해결하는 알고리즘이다. 즉, 2개의 포인터를 구간의 길이를 가변적으로 잡아가며 특정 조건을 만족하는 구간 혹은 값을 찾으면 된다. 이런 두 포인터는 mergesort에서 left와 right 같은 곳에서 이미 미 접한 적이 있을 것이다. 

 

이 2개의 포인터는 같은 방향으로 진행하기도 하고 양끝에서 시작하여 반대로 진행하기도 하며, 포인터 하나는 한쪽 방향으로만 진행하고 다른 포인터는 양쪽으로 이동하기도 한다. 즉, 가변적으로 문제에 맞게 방향이 설정이 되는 것이다. 이런 두 포인터의 시간 복잡도는 O(n)으로 선형 시간내에 문제 해결이 가능한 효율적인 알고리즘이다. 

 

알고리즘!

 이 문제는 두 수의 합의 절댓값이 0에 가까운 두 수를 찾는 것이다. 그리고 현재 정렬이 되어 있는 상태이다. 이때 두 포인터를 left와 right로 잡고 left는 배열의 맨 처음(1), right는 배열의 맨 마지막(n)으로 둔다. 알고리즘 진행 방식은 다음과 같다

 

 만약 left+right < 0 이라면 left가 right보다 절대값이 큰 것이다. 이때 만약 right를 하나 옮겨 right보다 작은 바로 다음 수를 right'가 가르킨다고 하면 다시 left+right를 하게 될 경우 left+right<left+right'<0이기 때문에 절대값은 |left+right|>|left+ right'|이 된다. 즉 0에 가까워지지 않다. 따라서 이 같은 경우에는 left를 하나 오른쪽으로 옮겨야 0에 가까운 수를 구할 수 있다.

 마찬가지로 left+right>0 이라면 right를 하나 왼쪽으로 옮겨야 0에 가까운 수를 구할 수 있다.

 

 left와 right가 만날 때까지 (모든 배열의 경우수를 탐색 했을 때까지) 0의 가까운 수가 나올 때마다 min_water의 저장하고 이때마다 index를 저장해두면 특성값이 0에 가까운 용액을 만들어내는 두 용액을 찾을 수 있다. 

 

 

깨달은 점!

 투 포인터는 특정한 경우에만 사용할 수 있다. 예를 이 문제와 같이 모든 값들이 오름차순으로 되어 있고 포인터 2개를 이용하여 한번의 조건식으로 포인터가 둘 중 하나가 이동하여 선형 시간내에 모든 배열의 값을 탐색할 수 있는 경우이다. 

 

 

소스코드

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<map>
#include<cstdlib>
#include<iomanip>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
int arr[100001];

int main() {    
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n,minus_index=0;
  cin>>n;
  for(int i=1;i<=n;i++){
     cin>>arr[i];
    if(arr[i]<0)
      minus_index=i;
  }
  
  if(minus_index==n) //모두 음수
  {
    cout<<arr[n-1]<<" "<<arr[n];
    return 0;
  }    
  if(minus_index==0) //모두 양수 
  {
     cout<<arr[1]<<" "<<arr[2];
    return 0;
  }   
   
  int min_water=2000000001,index1,index2,left=1,right=n,decision=0;
  while(left<right){
    int tmp=arr[left]+arr[right];
    if(tmp<0){
      tmp=tmp*(-1);
      decision=1;
    }
    else
      decision=0;
      
    if(min_water>tmp){
      min_water=tmp;
      index1=left, index2=right;
    }
    if(decision==1)
      left++;      
    else
      right--;     
  }

  cout<<arr[index1]<<" "<<arr[index2];
}