문제

입력 값으로 벡터와 목표 숫자를 받음

벡터 내에서 목표 숫자(target)을 만들 수 있는 두 수를 찾고, 그 수들의 index 값을 벡터 형태로 출력해야 함.

풀이

첫 번째 풀이 - 브루트 포스

일단 무지성으로 이중 for문을 돌려서 하나 하나 벡터를 iterate 하면서 값을 비교한 뒤, 두 수를 더해 target이 만들어지면 리턴하는 식으로 짜보았습니다.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i = 0 ; i < nums.size(); i++){
            for (int j = i+1; j < nums.size(); j++){
                if(nums[i]+nums[j] == target){
                    return {i,j};
                }
            }        
        }
        return {};
    }
};

시간 복잡도 O(N^2)를 가진다. 이렇게 해서 solved가 뜨긴 했지만,,, 더 최적화가 가능하다고 한다....

두 번째 풀이 - Hash 이용

Hash는 값을 찾을 때 O(1)의 시간 복잡도를 가진다.
리트코드에서 제공하는 튜토리얼 영상을 보니 Hash를 사용하여 최적화를 하였었는데,,.,.

public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashmap;        
        for(int i = 0; i < nums.size(); i++){
            int x = target - nums[i];
            if(hashmap.find(x) != hashmap.end()){
                return {i, hashmap[x]};
            }
            else
                hashmap[nums[i]] = i;
        }
        return {};
    }
};

unordered_map 자료구조를 사용하였는데... 키와 밸류를 같이 저장하는 구조임...

vector[i] + target - vector[i] = target 이기 때문에.....
vector[i] 동안 해쉬맵 안에 target-vector[i]가 있는지 확인하고 존재하지 않으면 해쉬맵에 해당 벡터의 값과 인덱스를 키,밸류로 넣어버림.

하 이게 이해는 잘 되는데 설명하기가 개 빡 세 네

그리고 unordered_map 의 find 멤버함수는 키 값을 입력받아 해당 키가 존재한다면 해당 키의 밸류를 리턴하는 함수임.

가정

vector [1,3,4,5,9] 라고 가정하고 target = 10이라고 가정해보자

첫 번째 iterate (i = 0) 에서 target - vector[i] = 10 - 1 = 9가 된다.

따라서 해쉬 맵 안에서 9를 찾으면 된다. 하지만 해쉬 맵이 비어있으므로 바로 else로 넘어가서 해쉬 맵의 vector[i] 부분에 i를 삽입한다...

여기서 좀 헷갈렸는데.. hashmap[nums[i]] = i 는 키 값으로 1을, 밸류는 1을 가르키는 인덱스 0 을 삽입함.

그 뒤로 계속 진행해가면서 해쉬맵을 채우다가...

i = 4 , 즉 9를 가르킬 때 x = 10 - 9 = 1이 됨.

해쉬맵에서 키값 1을 찾게 되고 우리는 i = 0 때 삽입했었던 {1:0} 값이 해쉬맵이 있다는 것을 알음...

따라서 9를 가르키는 인덱스 i와 해쉬 맵에서 1을 가르키는 0을 리턴하게 됨.