[LeetCode] Two Sum

https://leetcode.com/problems/two-sum/description/

Two Sum - LeetCode

 

 

03/06

class Solution {
public:
    bool vis[10001];

    int getIndex(vector<int>& nums, int val){
        for(int i = 0; i < nums.size(); ++i){
            if(nums[i] == val && !vis[i]){
                vis[i] = 1;
                return i;
            }
        }
        return -1;    
    }

    vector<int> twoSum(vector<int>& nums, int target) {
        memset(vis, 0, sizeof(vis));
        vector<int> ans;
        vector<int> sortedNums(nums);
        sort(sortedNums.begin(), sortedNums.end());
        for(auto itr = sortedNums.begin(); itr != sortedNums.end(); ++itr){
            int curr = *itr;
            bool flag = binary_search(next(itr), sortedNums.end(), target-curr);
            if(flag){
                ans.push_back(getIndex(nums, curr));
                ans.push_back(getIndex(nums, target-curr));
                return ans;
            }
        }
        return ans;
    }
};

 

97.74%

 

 

주어진 배열에서 합이 target이 되는 두 수의 index를 반환하는 문제입니다.

for(int i = 0; i < nums.size(); ++i){
	for(int j = i+1; j < nums.size(); ++j){
		if(nums[i] + nums[j] == target){
			ans.push_back(i);
			ans.push_back(j);
			return ans;
		}
	}
}

가장 naive한 풀이로는 위 코드처럼 이중 for문으로 배열을 순회하면서 합이 target이 되는 두 수를 찾는 O(N^2)의 풀이가 있습니다. 문제 난이도가 easy인 만큼 nums의 length가 최대 10^4이기 때문에 O(N^2)으로도 1초 내에 통과될 수 있습니다. 다만 문제 하단에 제시된 follow-up question을 보면 알 수 있듯 O(N^2)보다 효율적인 알고리즘이 있고 이것이 이 문제가 중요 문제로 분류되는 이유라고 생각합니다. 

 

우선 주어진 배열을 오름차순으로 정렬한 sortedNums 배열을 만듭니다.(O(NlogN)) 정렬을 하는 이유는 binary search를 이용하기 위함입니다. 일반적인 배열에 대해 특정 element를 search 하려면 O(N)이지만 정렬된 배열에 대해 binary search를 이용하면 O(logN)에 search할 수 있습니다. 배열을 순회하면서 해당 num과 더했을 때 target이 되는 값은 target-num이므로 binary_search를 통해 target-num이 배열 내에 존재하는지 확인합니다. 만약 존재한다면 원래 주어진 배열 Nums에서의 num과 target-num의 index를 반환하면 됩니다. 이 알고리즘은 매 num마다 배열에 target-num이 존재하는지 확인하는데 O(logN)이므로 시간복잡도는 O(NlogN)입니다. 존재할 경우 원래 주어진 배열 Nums에서 num과 target-num의 index를 확인하는 과정은 단 한 번 수행되므로 O(N)입니다. 따라서 O(NlogN)의 시간복잡도에 영향을 주지 않습니다.

 

주의할 점으로는 

nums = [3,3], target = 6

문제에서 주어진 상기 test case와 같이 num과 target - num이 같은 case가 있을 수 있으므로 vis 배열을 통해 중복된 index를 반환하지 않도록 체크해 줍니다. 만약 이러한 작업을 해주지 않는다면 ans에는 [0, 0]이 저장되어 잘못된 값을 반환하게 됩니다. 

 

슬라이딩 윈도우로도 불리는 투 포인터로도 풀 수 있겠습니다. 투포인터 문제들은 binary search로도 풀 수 있는 경우가 많고, 반대로 binary search로 풀 수 있는 문제들은 투 포인터로 풀 수 있는 경우도 많습니다. 따라서 이러한 문제들을 공부할 때 두 풀이 모두 고민해 보면 좋을 것 같습니다.