[Algorithm] 배열 내, 특정 조건을 만족하는 원소 쌍 검색하기

 

  배열이 주어지고, 배열 내에서 특정 조건을 만족하는 원소 쌍을 검색하는 문제 상황을 해결하는 방법에 대하여 공부해보자. 가령, 이런 상황이다. 

• 유한 길이의 1 - d array 가 주어졌을 때, 두 원소의 합이 targetNum 이 되도록 하는 원소 쌍을 찾아라.
• 어떠한 조합으로도 targetNum 을 만들 수 없다면 empty vector 을 반환하라.
• 두 원소의 합이 targetNum 이 되도록 하는 원소 쌍은 유일하다.

   면접에서 이 문제를 물어봤다고 가정하고, 차근차근 논리를 전개해보자. 먼저, 역으로 물어봐야 할 것은 어느 정도의 시간과 메모리를 허용하는지, 당연한 소리겠지만 원소의 타입은 integer 인지 그리고 2개의 원소에 대해서 조건을 만족하면 되는지, 반환해야하는 vector 내의 원소의 정렬 상태는 어떻게 되어야 하는지 등을 체크해보는 것이 좋겠다. 실행 시간과 메모리의 제약이 없는 상황이라면, 간단한 방법부터 제시해볼 수 있겠다.

 

  첫 번째 방법은 시간 효율은 좋지 않은 편이지만 구현이 간단하고, 이해하기 쉽다.

배열을 2번 순회한다. loop 에 사용하는 index 를 i, j 라고 가정하자. outer loop index 가 i 이고 inner loop index 가 j 인 것이다. 그러면, array[i] 에 대해서 원하는 조건을 만족하는 array[j] 를 검색한다. array[i] 와 array[j] 의 합이 targetNum 이 된다면, {array[i], array[j]} 를 반환한다. 이 방법은 시간 복잡도가 O(N^2) 이며, 공간 복잡도는 (1) 이다.

// Two Number Sum Solution 1
// Time complexity : O(N^2)
// Spae complexity : O(N) 
// 배열을 2번 탐색하여, 조건을 만족하는 pair 을 검출

#include <vector>

using namespace std;

// time  : O(N^2) 
// Space : O(1)
vector<int> twoNumberSum(vector<int> array, int targetSum) {
  // Write your code here.
  vector<int> ans; int present = 0;
  for(int i = 0 ; i < array.size(); i++){
    present = array[i];
    for(int j = i+1  ; j < array.size(); j++){
      if(present + array[j] == targetSum){
        return {present, array[j]};
      }
    }
  }
  
  return ans;
}

  위 방법을 보다 최적화할 수 있겠냐는 요구가 들어온다면, 더 효율적인 알고리즘을 구상해서 시간 복잡도를 줄이던가 혹은 공간 복잡도를 조금 희생해서 시간 복잡도를 줄이는 방안이 있겠다. 둘 중 어느 방향으로 생각하면 될 지 물어보고, 생각을 진행하자. 어느 방법도 상관없다고 하면, 공간 복잡도를 희생해서 시간 복잡도를 올리는 것이 보다 생각하기 쉬운 것 같다.

 

  두 번째 방법은 hash table 을 추가적으로 사용해서 공간 복잡도를 O(N) 으로 희생하는 대신 시간 복잡도를 O(N) 으로 optimize 하는 것이다.

먼저, array 내의 모든 원소를 hash table 에 insert 한다. 그리고 array 를 1번만 순회하면서(loop index 는 i), array[i] 와 matching 이 되면 우리가 만족시키고자 하는 조건을 통과할 수 있는 원소를 hash tabel 내에서 찾는다. 위 경우에는 array[i] + x = targetNum 이 되어야 하므로, x = targetNum - array[i] 가 hash tabel 내에 존재하는 지 찾아준다. 만약에 존재하면 {array[i], targetNum - array[i]} 을 반환하고, 존재하지 않으면 { } 을 반환한다.

// Two Number Sum Soltion 2
// hash table 을 이용한 풀이

#include <vector>
#include <unordered_set>
using namespace std;

// time  : O(N) || N is length of array
// Space : O(N)
vector<int> twoNumberSum(vector<int> array, int targetSum) {
  // Write your code here.
  unordered_set<int> s(array.begin(), array.end()); int candidate=0;
  for(auto ele : array){
    candidate = targetSum-ele;
    if(s.find(candidate)!=s.end() && candidate != ele)
      return {ele, targetSum-ele};
  }
  
  return {};
}

 

  세 번째 방법은 첫 번째 사용한 방법을 최대한 최적화하여 O(NlogN) 의 시간 복잡도에 , O(1) 의 공간 복잡도로 해결하는 것이다. 처음에 주어지는 배열이 만약 정렬된 상태라면, 배열의 첫 인덱스를 의미하는 left 와 배열의 마지막 인덱스를 의미하는 right 를 선언한 다음에 left 와 right 를 적절히 움직여가며 targetNum 을 만족하는 원소 쌍을 찾아낼 수 있다. 이 방법은 익히 투 포인터 알고리즘이라고 알려져 있다. Quick-sort 를 구현할 때 사용한 idea 와 조금 비슷한 느낌을 받는다. (여담으로 동일한 구조로, left, right 를 갱신할 때 마다 탐색 범위가 절반씩 줄어들게 만들면 그게 바로 바이너리 서치이다.)

// Two Number Sum solution3
// Two pointers Algorithm

#include <vector>
#include <algorithm>

using namespace std;
// time  : O(NlogN) || N is length of array
// Space : O(1)
vector<int> twoNumberSum(vector<int> array, int targetSum) {
  // Write your code here.
  sort(array.begin(), array.end()); int current = 0;
  int left = 0; int right = array.size()-1;
  while(left<right){
    current = array[left]+array[right];
    if(current == targetSum) return {array[left], array[right]};
    else if(current < targetSum){
      left++;
    }
    else if(current > targetSum){
      right--;
    }
  }
  return {};
}

https://github.com/versatile0010/AlgoExpert