[Easy] Leetcode | 1. Two Sum | Array, Hash table

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

- 문제
integer를 요소(원소)로 가지는 array(nums)와 target이 주어진다.
array의 요소 중 2개의 요소를 더해 target을 만드는 요소의 인덱스 2개를 반환하는 함수를 만드는 문제이다.
정답은 정확히 1개가 존재하며, 동일한 요소를 중복으로 사용할 수 없다고 가정한다.
위의 예를 보면 2와 7을 더하면 target이 되므로 0과 1이 담긴 배열을 반환하면 정답이다.

- 풀이
우선 크게 2가지 방법이 있다.
첫 번째 방법은 이중 루프를 사용하여 모든 경우를 한 번씩 확인하는 것이다. 따라서 이 경우 모든 조합을 다 체크하므로 시간복잡도는 n*(n-1)/2  => O(n^2)이 될 것이다. 그리고 반복 횟수와 상관없이 반환할 요소는 2개이므로 공간 복잡도는 O(1)이 될 것이다.
다음은 첫 번째 방법을 이용한 코드이다.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        /*
            1. 2중 루프 사용
            - 바깥 for문은 nums의 size만큼 반복하고
            - 내부 for문은 바깥 인덱스의 +1 부터 더하며 target과 일치하는지 확인
        */
        
        vector<int> ret;
        ret.reserve(2);
        for(size_t i = 0; i != nums.size(); ++i)
        {
            for(size_t j = i+1; j != nums.size(); ++j)
            {
                if(nums[i] + nums[j] == target)
                {
                    ret.push_back(i);
                    ret.push_back(j);
                    return ret;
                }
            }
        }
        
        return ret;
    }
};

단순하며 간단한 방법으로 nums의 각 요소마다 다른 요소들을 한 번씩 조합하며 더해 target과 일치하는지 확인한다.
일치한다면 해당 인덱스를 ret 벡터에 저장한 후 ret 벡터를 반환하면 된다.

두 번째 방법은 해쉬맵을 이용하는 방법이다. 맵은 key와 value를 쌍으로 저장하는 자료구조이며 대략적인 설계는 다음과 같다.
우선 루프를 돌 때마다 map에 (nums[i], i) 쌍으로 저장한다. 즉 문제의 예로 보면 (2, 0), (7, 1) ... 과 같은 쌍으로 저장할 것이다. 
그리고 루프 시작 시 임시 변수에 target에서 nums[i]을 뺀 값을 저장해둔다. 이 값은 현재 요소인 nums[i]와 더하면 target이 된다.
즉 target-nums[i]이 map의 key에 존재한다면 현재 인덱스와 찾은 key의 value가 정답이다.
이 경우 루프를 최대 n번 반복하므로 시간 복잡도는 O(n)이며, 공간복잡도는 요소를 최대 n개 만큼 저장할 수 있으므로 O(n)이다.
코드는 다음과 같이 작성하였다.

#include <unordered_map>

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        /*
            2. 해쉬맵 사용
            - 루프를 돌면서 key에 요소를 저장
        */
        unordered_map<int, int> myMap;
        vector<int> ret;
        size_t numSize = nums.size(); 
        for(size_t i = 0; i != numSize; ++i)
        {
            int val = target-nums[i];
            if(myMap.find(val) != myMap.end())
            {
                ret.push_back(i);
                ret.push_back(myMap[val]);
                return ret;
            }
            else
            {
                myMap[nums[i]] = i; 
            }
        }
        
        return ret;
    }
};

 
 C++에서 해쉬맵은 unordered_map이며 요소를 정렬하지 않는다. map은 key를 기준으로 정렬을 하여 저장하는 자료구조이므로 느리다. 또한 해쉬맵은 인덱스를 통한 접근을 지원하므로 요소 액세스 시 시간 복잡도가 O(1)이다.
임시 변수 val에 target-nums[i]를 저장 후, 맵에 저장된 key 중 val이 존재한다면 nums[i]와의 합이 target이므로 정답을 찾은 것이다. 따라서 ret 벡터에 두 인덱스를 저장 후 반환한다. 찾지 못했을 경우 맵에 현재 요소와 인덱스를 저장한다.

다음은 두 방법에 대한 각각의 소요 시간 분포 그래프이다.

첫 번째 코드
120ms가 소요되었으며 내 해법의 대략적인 위치이다.

두 번째 코드
8ms가 소요되었으며 대략적인 위치이고 첫 번째 방법보다 훨씬 빠르다.