[LeetCode-1-c++]Two Sum

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

Two Sum - LeetCode

LeetCode 1번 Two Sum 문제입니다. 

Input 값으로 integer 배열인 nums와 integer target이 주어진다고 합니다.

nums 배열의 값들 중 두개를 더해서 target 이 되는 값의 인덱스들(indices)을 [int, int]로 return 해주면 되는데,

하나의 답만 존재하며 같은 요소의 값을 중복해서 사용하지 않는다고 합니다.

 

저는 두가지 방법으로 풀었습니다. 처음에는 <algorithm>의 find함수를 이용하는 방법인데요, 

풀기 전 생각했던 아이디어로 {find(시작점, 끝점, 찾는 값) - begin 이터레이터}를 사용하면 찾는 값의 index가 반환되니,

for문으로 nums를 돌리며 target-nums[i]의 값이 nums 에 존재할 경우 i 와 위에서 표시한 { } 안의 값을 vector에 push해 답으로 return 해주면 될 것 같다는 생각이 들었습니다. 

 

그렇게 해서 풀이한 결과, 하단의 코드를 작성할 수 있었습니다.

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

이렇게 풀고 나니, 궁금증이 생겼습니다.

vector<int>tmp = nums 라 해서, nums의 값들을 모두 복사해서 사용했는데, 이게 필요한 과정일까? 만약에 10개의 값들 중 앞의 2개에서 답이 나와버리면 break로 나오긴 하지만 복사하는 과정이 불필요했던 일은 아닐까?

또, nums.begin() 을 빼서 인덱스를 구해줘야 하는데, 이걸 다르게 표현하는 방법이 없을까? 

마지막으로 더 빠른 방법은 없을까?

 

그래서 이번에는 unordered_map을 사용해서 구현해보았습니다.

unordered_map은 hash 방식 map은 균형 이진 트리로 구성되어 있죠.

문제에서는 정렬되어 정보가 저장될 필요가 없기도 하니 더 빠른 unordered_map을 택하였습니다.

우선 기존과 같은 방식으로 for문을 돌리는 것과 빈 unordered_map을 선언해서 unordered_map.find(target-nums[i])가 있을 경우는 유사하게 진행했습니다.

 

이제 조금 달라진 것이 만약 처음 for문을 돌리면 map에는 아무 값도 없으므로 unordered_map.find를 사용해가기 위해선 어떤 값을 넣어야 할 것입니다. 때문에 unordered_map[nums[i]] = i 이런 식으로 선언하면 begin 이터레이터를 빼주지 않아도 인덱스와 값이 서로 바뀌어 저장될 것입니다. 물론 표현이 그렇다는 것이지 실제로는 key, value 쌍으로 저장될 것입니다. 때문에 index 낭비도 없으므로 해당 아이디어에 적합한 구조라고 생각했습니다. vector를 다시 사용해볼까도 했었지만 중간에 값을 삽입하려면 insert를 사용해야 하는데, 그러면 중간에 삽입되고 index의 값은 밀리게 되므로 원하는 결과를 얻을 수 없기도 하고, 속도적인 측면에서도 느리기에 해당 아이디어는 깔끔하게 접었습니다.

 

위 로직대로 순서대로 탐색하며 ans와 맞는 조건이 나오면 break문을 걸지 않고 return ans로 함수를 나올 수 있게 될 것입니다. 대략의 아이디어는 위와 같았고, 결과적으로 하단의 코드처럼 작성하게 되었습니다.

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

 

훨씬 빨라졌습니다! 이제 막 코딩테스트 문제 풀이를 시작했지만 여러 가지 풀이 방식을 고민해보고 정답을 맞추니 괜히 뿌듯한 기분이 듭니다. 앞으로도 여러 경우로 풀어보고 서로 비교해봐야겠다는 생각이 드네요:D 

꾸준히 문제 풀이 해 보는 것을 목표로 오늘도 화이팅 :)!!