[LeetCode] 1. Two Sum(Swift, C++)

안녕하세요.

오랜만에 알고리즘 문제 포스트를 하게 되었습니다.

 

프로젝트를 시작한 이후로 알고리즘을 소홀히 하면서 감이 자꾸 떨어져서 다시 알고리즘도 틈틈히 해보려고 합니다.

 

문제는 블라인드에서 추천하는 문제들부터 차근차근 풀어보려고 합니다.

 

아 그리고 이번 포스트부터 Swift와 C++ 두가지 버전으로 풀어보겠습니다.

 

오늘의 문제는 Two Sum이고 LeetCode의 첫번째 문제입니다.

(링크: https://leetcode.com/problems/two-sum/)

 

1. Int형 배열에서 2개의 숫자의 합이 target(Int) 되는 배열의 index를 return 하기

우선 가장 쉽게 생각해 볼 수 있는 방법은 Brute Force, 간단히 말해 모든 경우의 수를 탐색하는 방법으로 작성해보겠습니다.

 

Brute Force

• C++

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

결과

Runtime: 8 ms, faster than 95.67% of C++ online submissions for Two Sum.

Memory Usage: 9.4 MB, less than 63.15% of C++ online submissions for Two Sum.

(생각보다 너무 빨라서 당황...)

 

• Swift

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        //Brute Force
        for i in 0..<nums.count{
            for j in (i+1)..<nums.count{
                if nums[i] + nums[j] == target{
                    return [i, j]
                }
            }
        }
        return []
    }
}

결과

Runtime: 36 ms, faster than 66.49% of Swift online submissions for Two Sum.

Memory Usage: 13.7 MB, less than 97.50% of Swift online submissions for Two Sum.

 

C++ 결과가 예상보다 좋게 나와서 당황스럽지만

우선 시간복잡도를 보면 for문을 2개 쓰기 때문에 O(n^2)인 시간복잡도를 가진 코드입니다.

 

좀 더 효율적인 코드를 고민해보자면

배열의 각 숫자들은 자기 자신과 더해질 수는 target이 될 다른 숫자가 필요합니다.

따라서 nums[i]와 target - nums[i]가 존재한다면 그 요소의 index가 답이 되겠죠

 

예를 들어, nums = [2,7,11,15], target = 9가 주어진 다면 i = 0일때 target - nums[0]인 7이 존재한다면 [0, (7이 있는 index)]가 답이 되겠습니다. 이걸 효율적으로 저장한다면 Hash Table, c++에서는 map, Swift에서는 Dictionary로 해결이 가능할겁니다.

Hash Table

• C++

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]]);
                return ans;
            }
            m[nums[i]] = i;
        }
        return {};    
    }
};

결과

Runtime: 8 ms, faster than 95.67% of C++ online submissions for Two Sum.

Memory Usage: 9.2 MB, less than 98.07% of C++ online submissions for Two Sum.

(똑같다니...)

 

• Swift

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        //Hash Map
        var dict: [Int: Int] = [:]
        for i in 0..<nums.count {
            let ans1 = nums[i]
            let ans2 = target - ans1
            if let j = dict[ans2] {return [j,i]}
            dict[ans1] = i
        }
        return []
    }
}

결과

Runtime: 32 ms, faster than 81.94% of Swift online submissions for Two Sum.

Memory Usage: 14.1 MB, less than 79.74% of Swift online submissions for Two Sum.

 

C++ 결과가 여전히 이상하지만 테스트 케이스가 시간복잡도랑 의미없게 잡힌거같습니다...

 

아무튼 각 hash table에 해당 nums[i]와 target이 되는 key-value가 존재한다면 각 index를 return함으로써

for문 하나의 값을 찾을 수 있는 즉, 시간복잡도 O(n)을 만족하는 코드를 작성할 수 있게되겠습니다.

 

오늘도 부족한 글 읽어주셔서 감사합니다!