LeetCode - 1. Two Sum

문제 링크입니다 : https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

 

이 문제는 두 가지 방법으로 풀 수가 있다.

 

첫 번째로 브루트 포스 문제로 풀 수 있는데, 정말 간단하게 모든 경우의 수를 다 돌려보면 된다.

 

그런데 문제에서 인풋에 대한 정보가 없고, 제한 시간에 대한 정보도 없다. 인풋이 둘 다 적당히 적다면 브루트 포스도 괜찮은 것 같다.

하지만 인풋이 조금만 커지면 총 시간복잡도가 O(N^2)이 걸리기 때문에 효율적이지 않다.

 

 

 

 

두 번재는 map을 이용하는 방법이다. map의 key 값으로는 "입력으로 주어진 숫자"를 넣고 value값으로 인덱스를 넣어주면, 탐색할 때 O(logN)이면 끝난다. 그래서 이 문제의 총 시간 복잡도를 O(NlogN)으로 끝낼 수 있다.

 

 

 

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        /*
        vector<int> ret;
        for(int i = 0; i < nums.size(); i++) {
            for(int j = i + 1; j < nums.size(); j++) {
                if(target == nums[i] + nums[j]) {
                    return ret = {i, j};
                }
            }
        }
        return ret;
        */
        
        
        map<int, int> m;
        map<int, int>::iterator iter;
        for(int i = 0; i < nums.size(); i++) {
            iter = m.find(target - nums[i]);
            if(iter == m.end()) {
                //추가
                m[nums[i]] = i;
            } else {
                //찾음
                return {(*iter).second, i};
            }
        }
        return {};
    }
};

 

 

 

JAVA

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // for(int i = 0; i < nums.length - 1; i++) {
        //     for(int j = i + 1; j < nums.length; j++) {
        //         if(target == nums[i] + nums[j]) {
        //             return new int[]{i, j};
        //         }
        //     }
        // }
        // return null;   
        
        Map<Integer, Integer> m = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            int cur = nums[i];
            if(m.containsKey(target - cur)) {
                return new int[]{m.get(target - cur), i};
            } else {
                m.put(cur, i);
            }
        }
        return null;
    }
}

 

 

 

 

 

Python3

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # for i in range(len(nums) - 1):
        #     for j in range(i + 1, len(nums)):
        #         if target == nums[i] + nums[j]:
        #             return [i, j];
        # return [];
        m = {}
        for idx, num in enumerate(nums):
            if target-num in m:
                return [m[target-num], idx]
            m[num] = idx

 

 

 

 

 

개발 환경 : vscode

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~