[LeetCode] C++ 1. Two Sum

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

문제

문제 분석

- bruteforce로도 풀 수 있겠지만, 실행 시간을 줄이기 위해서 하나의 숫자를 고르고, Target 값에서 그 숫자를 뺀 값을 찾는 방식으로 푸는 것이 낫다고 생각하였습니다.

 

풀이 1

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); ++i) {
            int complement = target - nums[i];
            auto iter = find(nums.begin(), nums.end(), complement);
    
            if (iter != nums.end() && iter - nums.begin() != i) {
                return {i, static_cast<int>(iter - nums.begin())};
            }
        }
        return {};
    }
};

vector를 그대로 find로 하나씩 둘러보면서 찾으니 시간이 상당히 오래 걸렸습니다. 그래서 해쉬된 값을 통해 빠르게 접근하기 위해서 unordered_map을 사용하기로 하였습니다. 

 

풀이 2

#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> numMap; 

        for (int i = 0; i < nums.size(); ++i) {
            numMap[nums[i]] = i;
        }

        for (int i = 0; i < nums.size(); ++i) {
            int complement = target - nums[i];
            auto it = numMap.find(complement);

            if (it != numMap.end() && it->second != i) {
                return {i, it->second};
            }
        }
        return {};
    }
};

unordered_map을 통해 탐색하니 속도가 상당히 개선되었습니다.