[ leetcode 문제풀이 ] Two Sum

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

Two Sum - LeetCode

(Two Sum 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Two Sum 문제 설명 >

 

Two Sum 문제는 다음과 같다.

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

 

주어진 정수 배열 nums와 정수 target이 주어질 때, 더해서 target이 되도록 하는 두 숫자의 인덱스를 리턴하여라.

각 입력에 대해서는 정확히 하나의 해답이 있다고 가정해도 좋고, 동일한 원소를 두 번 사용할 수 없다. 답은 어떤 순서로든 반환할 수 있다.

 

다음 세 가지 출력 예시가 주어졌다. 

 

 

주어진 제한 조건은 2 ≤ nums.length ≤ 10^4, -10^9 ≤nums[i] ≤ 10^9,  -10^9 ≤ target ≤ 10^9 과 오직 하나의 답만 존재한다는 것이다.

Follow up question으로는 O(n^2)의 시간복잡도보다 적게 걸리는 알고리즘을 만들 수 있는가? 이다.

 

 

 

---

< Two Sum 문제 접근 - 기본 >

 

가장 간단한 방법으로는 가능한 두 개의 숫자 조합을 모두 탐색해보며 두 숫자의 합이 target과 같아지는지를 확인하는 것이다. 이를 코드로 나타내면 다음과 같다. (Cpp 사용)

 

vector<int> twoSum(vector<int>& nums, int target) {
    vector<int> ans;
    for(int i=0;i<nums.size()-1;i++)
        for(int j=i+1;j<nums.size();j++)
            if(nums[i]+nums[j] == target){
                ans = {i,j};
                break;
            }
    return ans;
}

 

위 경우 가능한 모든 조합의 경우의 수(nC2)를 탐색하므로 O(n^2)의 시간복잡도를 가짐을 알 수 있다.

물론 이는 너무 느린 방법이기 때문에 성에 차지 않는다. 

 

 

 

---

< Two Sum 문제 접근 - 심화 >

 

앞서 작성한 알고리즘을 보며 이런 생각을 할 수 있다. 하나의 숫자를 정했을 때, 꼭 모든 index를 훑으며 합이 target이 되는 숫자가 있는지를 확인해야 할까? 꼭 모든 범위를 확인하지 않도록 하려면 역시 미리 정렬해두는 것이 제격일 것이다. 

 

nums 배열에 대해 정렬된 배열 sorted_nums을 새로 만들자. 이제 sorted_nums의 첫번째 원소부터 마지막 원소에 대해 target - sorted_nums[i] 이 sorted_nums 배열에 존재하는지를 탐색한다. 만약 존재한다면 sorted_nums[i]와 target - sorted_nums[i]를 저장하고 다시 처음의 nums 배열로 돌아온다. nums 배열에서 sorted_nums[i]와 target - sorted_nums[i]가 속한 index를 찾아 리턴하면 되는 것이다. 

 

time complexity를 생각해보면 sorted_nums를 만드는 과정에서 quick sort를 사용하면 O(n log n),

sorted_nums의 원소를 순회하는 횟수(n) * target - sorted_nums[i]를 찾는 binary search (O(log n)) = O(n log n),

nums 배열에서 원래의 index 찾기 O(n) 으로

이 알고리즘은 O(n log n) < O(n^2)임을 알 수 있다. (Follow up question 충족!)

 

전체 코드로 나타내면 복잡하다 보니 간단한 흐름만 나태나어 보았다. (Cpp 사용) 

 

#include <algorithm>
using namespace std;
    
bool binSearch(vector<int>&A, int low, int high, int target){} // 존재하면 true, 아니면 false
    
vector<int> twoSum(vector<int>& nums, int target){
    int n = nums.size();
    vector<int> sorted_nums(n);
    for(int i=0;i<n;i++)
        sorted_nums[i] = nums[i];
    sort(sorted_nums.begin(), sorted_nums.end());
        
    int x;
    for(int i=0;i<n;i++)
        if(binSearch(sorted_nums, 0, n-1, target - sorted_nums[i])){
            x = sorted_nums[i];
            break;
        }
    
    vector<int> ans;
    for(int i=0;i<n;i++){
        if(nums[i] == x)
            ans.push_back(i);
        else if(nums[i] == target - x)
            ans.push_back(i);
        if(ans.size() == 2)
            break;
    }
    return ans;
}

 

맨 처음 방법에 비해선 확실히 더 좋은 속도를 보인다. 다만 문제는 코드가 너무 길고 보기 싫다.

이번엔 hash table을 사용해 좀 더 간단하게 만들어보자.

 

cpp의 unordered_map은 STL 표준 Container로써 hash table 기반의 hash container이다. 따라서, 탐색하는 데 평균적으로 O(1)의 시간복잡도를 나타내는 유용한 도구라고 할 수 있다. unordered_map의 함수 find를 이용해 알고리즘으로 구현하는 방법을 알아보자. 

 

먼저 작성한 코드는 다음과 같다. (Cpp 사용)

 

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, vector<int>> numsMap;
    for(int i=0;i<nums.size();i++)		// (1)
        numsMap[nums[i]].push_back(i);
    
    vector<int> ans;
    for(auto elem = numsMap.begin(); elem != numsMap.end(); elem++){
        auto check = numsMap.find(target - elem->first);		// (2)
        if(check != numsMap.end() && (elem != check || elem -> second.size() == 2)){	//(3)
            ans.push_back(elem -> second[0]);
            elem -> second.erase(elem->second.begin());		// (4)
            ans.push_back(check -> second[0]);
            break;
        }
    }
    return ans;
}

 

코드의 핵심부분 (1) ~ (4)에 대한 설명은 다음과 같다.

 

(1) nums의 원소(합으로 target을 만들 게 되는 숫자)를 key 그것이 포함된 index를 value로 갖는 numsMap이라는 unordered_map(hash table)을 정의한다. 이때, index를 int의 vector로 받는 이유는 같은 숫자를 여러 index에서 갖고 있는 경우도 고려해주기 위함이다. (ex- input: nums=[3,3], target=6 ,then numsMap[0] = {0,1})

그렇다면, numsMap[i] = nums[i]라고 하면 vector<int>로 받을 필요가 없지 않을까! 싶지만, 그렇게 되면 hash table의 장점인 O(1)의 탐색 속도를 활용하지 못하게 된다. find 함수는 unordered_map의 key값에 대한 탐색이므로 어쩔 수 없이 이렇게 처리해주었다.

 

(2) numsMap의 모든 key 원소(nums[i])를 훑으며 target - nums[i]를 key로 하는 쌍이 있는지를 check에 저장한다.

만약 존재한다면 key의 위치에 대한 iterator가 저장되어 있을 것이고, 존재하지 않는다면 numsMap.end()위치가 저장된다.

 

(3) two sum을 만족하려면 find 함수로 저장한 check가 numsMap.end()를 가리키지 않아야 한다.

그리고, check가 지금 현재 고정한 하나의 값(elem)과 같은 iterator을 가리키지 않아야 한다. 이는 곧 같은 원소를 두 번 선택하는 것과 같기 때문이다. 그러나, elem의 value: elem의 key값을 원소로 갖는 nums배열의 index vector가 크기 2인 벡터이면 예외적으로 허용한다. 같은 숫자를 갖는 index가 2개라는 것이기 때문이다. 

 

(4) 찾아낸 두 숫자에 해당하는 index(elem -> second[0], check -> second[0])을 리턴하고자 하는 정답 vector ans에 넣는다. 이때, input이 nums=[3,3], target=6과 같이 주어진 경우 elem과 check는 같은 위치를 가리키는 iterator이며 
elem -> second이 크기 2인 벡터이기 때문에 약간의 조작을 가해주었다. 

elem -> second[0]을 ans에 넣은 후 elem -> second[0]을 value vector에서 삭제해 check에서 value에 접근했을 때 같은 index를 두 번 호출하지 않도록 하였다. 

 

이렇게 구하고자 하는 ans vector를 오류 없이 리턴할 수 있다.

 

처음 생각한 것에 비해 고려해줘야 하는 케이스(ex- check가 elem과 같은 위치의 iterator인경우, 같은 숫자를 갖는 index가 여러개인 경우 등)가 많아서 어려웠다. 그래서 처음 구상한 것에 비해 다소 복잡해졌다.

 

Complexity Analysis를 하면 unordered_map 탐색에 O(n), unordered_map 내에서 find에 O(1)으로

총 O(n)의 시간복잡도를 가짐을 알 수 있다.