[LeetCode C++] 1. Two Sum

⭐️ 난이도

Easy

---

⭐️ 문제

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

Two Sum - LeetCode

int형 배열 nums와 int형 변수 target이 주어진다.

배열 nums에서 두 개의 수를 골라 그 값이 target이 되도록 하고자 할 때, 두 개의 수의 index를 구하시오.

단, 원소의 중복 사용은 불가능하며 target이 되는 조합은 오직 1개만 존재한다.

 

---

⭐️ Follow-up

Can you come up with an algorithm that is less than O(n^2) time complexity?

 

---

⭐️ Idea flow

문제 자체는 쉬운 문제였다. 하지만 시간 복잡도를 O(n^2) 밑으로 내리려면 중복 for문을 쓰지 않아야 한다.

 

첫 번째로는 two point를 생각했다. 하지만 two point는 정렬이 되어있는 상태에서 사용해야 하고, nums 배열을 무작정 sorting하면 해당 값이 몇 번째 index인지 알 수 없어져 버리기 때문에 해당 방법은 적절치 않다고 판단했다.

 

두 번째로는 backtracking을 생각했다.

해당 방법을 이용하면 DFS로 진행하다가 적절하지 않은 상황에는 백트래킹을 통해 되돌아가는 방식이다.

그런데 생각을 해보니 선택하는 원소의 개수가 2개이기 때문에 백트래킹을 하는 큰 의미가 없다고 생각을 했고, worst case에 시간 복잡도가 O(n^2)가 될 것이라고 예상을 했다.

 

그래서 결국 간단하게 구현이 가능한 이중 for문으로 구현을 했다.

기본적으로 모든 경우의 수를 확인하다가 원하는 경우를 발견하게 되면 vector<int> result에 담고 result를 반환했다.

---

⭐️ Code

class Solution {
public:
    
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result(2, 0);
        int num_size = nums.size();

        for (int i = 0; i < num_size; i++) {
            for (int k = i + 1; k < num_size; k++) {
                if (nums[i] + nums[k] == target) {
                    result[0] = i;
                    result[1] = k;
                    return result;
                }
            }
        }

        return result;
    }

};

 

 

---

⭐️ Feedback

https://leetcode.com/problems/two-sum/discuss/387760/C%2B%2B-O(n)-Solution-with-Explanation 

unordered_map을 사용해서 시간 복잡도를 O(n)까지 줄일 수 있었다.

unordered_map (이하 hash)의 key에는 실질적으로 배열에 들어가있는 값을, value에는 배열의 index값을 넣는다.

 

이후에 for문을 전체적으로 돌면서

1) 만일 [target - nums 배열의 현재 값]에 해당하는 key 값이 hash에 없다면, <num 배열의 현재 값, num 배열에서의 인덱스 값>을 넣는다.

2) 만일 [target - nums 배열의 현재 값]에 해당하는 key 값이 hash에 있다면, 이 말은 곧 현재 값과 더하여 target을 만들 수 있다는 뜻이 된다.

따라서 현재의 index (즉, i)와 hash의 value값을 return 하면 된다.

 

[전체 코드 보기]

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
		// Keys are the array values and values are the associated array indices
        unordered_map<int, int> hash; // Use as a hash table, instead of creating one
        vector<int> result;
        for (int i = 0; i < nums.size(); i++)
            if (hash.count(target - nums[i])) // If the partner of this value to reach the target sum has been saved already
            {
                result.push_back(hash[target - nums[i]]); // Get index of other value
                result.push_back(i);
                return result;
            }
            else // Pair has not yet been found, so save value to hash table
                hash[nums[i]] = i;
        return result;
    }
};

 

 

Top K Frequent Words 문제에 이어서 unordered_map을 유용하게 사용할 수 있는 문제였다.

unordered_map이 hash table 기반이라 탐색에 O(1) 소요되기 때문에 빨리 접근하여 속도를 줄일 때, 두 개의 값이 하나의 쌍을 이룰 때에 유용하게 사용되는 것 같다.

아직 leet code에서 두 문제 밖에 풀지 않았지만 unordered_map이 이렇게 유용하게 쓰인다니..

다른 사람의 코드를 분석하는 것이 얼마나 중요한 일인지 느끼게 된다. 끝!