Two_Sum(LeetCode)

(출처) https://leetcode.com/problems/two-sum

O(N^2)의 풀이

최대 10,000 개의 원소를 갖는 숫자 배열과 인트 정수 target 입력으로 들어온다.

서로 합하였을 때 target값이 되도록하는 배열의 인덱스 2개를 찾아서 리턴해주면 되는 문제.

배열의 모든 원소에 대하여 다시 배열의 모든 원소와 1:1 매칭해주면서(N * N), 합하여 target 값이 되는 원소 두 쌍을 찾으면 시간복잡도 O(N^2)으로 충분히 해결할 수 있는 문제다.

그런데 문제의 Follow-up 조건에서는 O(N^2) 미만의 로직을 짜낼 수 있는지를 묻는다.

이것저것 방법을 한번 생각해내봤지만 가지치기를 통하여 약간의 최적화로 평균을 O(N * logN) 정도로 낮추는 로직밖에 짜내지 못했다. (결국 최악의 경우 O(N^2)의 되는 로직)

하지만 다른 분들의 풀이를 보니 굉장히 간단한 방법으로 O(N)이 되게끔 할 수 있는 로직이 존재한다.

처음 순회로 원하는 자료를 미리 메모이제이션 해놓고 다시 순회하여 정답을 구하는 방식이었다.

조금 더 자세히 말하면, 먼저 입력 배열 전부 순회하면서 모든 배열 원소를 하나씩 꺼내 target과의 차 값을 구한다. (target - 배열원소)

구해놓은 차 값들은 따로 HashTable 자료구조에 저장해놓는다.

이후 다시 배열을 순회하면서 차 값에 해당하는 원소가 배열에 존재하는 지 확인하는 방식이면 결국 배열을 2번만 순회하여도(N+N) 문제에서 요구하는 두 값을 구해낼 수 있다.

따라서 O(N)이면 충분히 해결해진다.

굉장히 간단한데 이 방법을 생각해내지 못한게 많이 아쉽기도하고, 또 문제에서 요구하는 이런 사고방식?이 나중에 응용하기도 좋고 너무 괜찮았던 것 같아서 Good Solution 코드와 같이 따로 기록해 남겨두기로 했다.

코드 O(N^2)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    static vector<int> twoSum(vector<int>& nums, int target) {
        vector<pair<int,int>> nums_pair;
        for(int i = 0; i < nums.size(); i++) nums_pair.push_back(make_pair(nums[i], i));
        sort(nums_pair.begin(), nums_pair.end());

        for(int i = 0; i < nums_pair.size(); i++) {
            for(int j = nums_pair.size() - 1; j >= i; j--) {
                int addTwo = nums_pair[i].first + nums_pair[j].first;
                if (addTwo == target) {
                    return vector<int>{nums_pair[i].second, nums_pair[j].second};
                }
                if (addTwo < target) {
                    break;
                }
                else continue;
            }
        }

        return vector<int>{0}; // no answer
    }
};

int main() {
    vector<int> nums = {3,2,4};
    vector<int> result = Solution::twoSum(nums, 6);
    for(int i : result) {
        cout << i << " ";
    }
}

코드 O(N)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> indices;
            unordered_map<int,int> map; // key - value , data - index
            for ( int i=0; i<nums.size();i++){
                if(map.find(nums[i]) != map.end()){
                    indices.push_back(map.find(nums[i])->second);
                    indices.push_back(i);
                    break;
                }
                map.insert(make_pair(target-nums[i],i));
            }
            return indices;
    }
};