[C++] Leetcode - Two sum (Hash Map)

프로그래머스보다 Leetcode 에 더 양질의, 좋은 자료가 많은 것 같아서 옮겨탔습니다. 특히 해외 빅테크 기업들의 코딩 인터뷰 문제들도 있다고하는데, 대부분 유료라... 무료 위주의 탑 100개 알고리즘을 풀어보는 게 목표입니다.

---

문제 정의

---

---

벡터 리스트가 주어졌을 때, 두 원소의 합이 target이 되는 인덱스 값을 반환하는 문제입니다. 완전 탐색으로 쉽게 풀 수도 있지만, 그렇게하면 시간복잡도가 O(n^2)이 되기 때문에 많이 느리더라구요. 본 문제는 구글 코딩 테스트 관련, 구글에서 공식적으로 제공하는 유튜브 영상에도 수록된 문제입니다.

---

접근 방법

• Hash map의 key, value 형태를 활용합니다. Map은 순서가 있는 해시인데, 사실 꼭 순서가 중요하진 않습니다. 공부해볼 겸 Map을 가져다 사용했습니다.
• for문을 돌려서 어레이의 원소에 차례대로 접근합니다. 그리고 해당 원소의 값을 키로, 값을 value로 insert합니다.
• target으로부터의 차이값을 계산하여 해당 차이만큼에 해당하는 key를 가진 원소가 과거에 있었는지를 봅니다. 있었다면 합이 target이 되는 원소가 있었다는 뜻이니, 차례대로 인덱스값을 answer에 push_back해줍니다.

---

Map 정리

기본적으로 map을 c++에서 활용하기 위한 몇가지 구문을 정리해봤습니다. map은 키 값을 기준으로 order되는 형태이기 때문에 erase할 때 유용하게 사용될 수 있는 것 같습니다. (인덱스 범위로 삭제) 그리고 find하는 시간복잡도는 O(1)이므로 빠릅니다.

• 선언: map<int, int> m; m[2] = 1;
• 삽입: m.insert({3, 1}); (앞에가 key, 뒤에가 value)
• 찾기: m.find(3); if (m.find(key) != m.end()) {}; 키값을 검색하고, 마지막까지 찾으면 m.end()를 반환.
• 찾기2: for (auto it = m.begin() ; it != m.end(); it++) { cout << it->first << " " << it->second << endl; }`
• 기타: 여기 블로그에 잘 정리되어 있어서 링크 남깁니다.

---

코드 및 결과

• Runtime: 60 ms, faster than 39.22% of C++ online submissions for Two Sum.
• Memory Usage: 11.2 MB, less than 22.53% of C++ online submissions for Two Sum.

---

    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> answer;
        map<int, int> m;
        for (int i =0; i<nums.size(); i++) {
            
            m.insert({nums[i], i});
            if (m.find(target-nums[i]) != m.end() && m[target-nums[i]] != i) { 
                answer.push_back(m[target-nums[i]]);
                answer.push_back(i);
                cout << "found!\n";
                break;
            }
            
            
            // 완전탐색
            // for (int j=i+1; j<nums.size(); j++) {
            //     if (nums[i] + nums[j] == target) {
            //         answer.push_back(i);
            //         answer.push_back(j);
            //     }
            // }
            
        }
        
        return answer;   
    }

___