[Leet code - 1] Two Sum ✅

문제

정수배열 nums와 정수  target이 주어진다.

더해서 target이 되는 nums의 인덱스들을 반환해라.

 

같은 index는 사용 불가능하고, 답은 오직 하나라는 가정하에 풀이한다.

 

 

시간 복잡도

테스트 케이스가 1000개이므로,  $O(n^2)$까지 아슬아슬하게 가능하다.

 

 

해결 방안

먼저 제일 떠오른 건 만만한 완전탐색으로, 모든 경우의 수를 구해보는 이중 반복문이 있다.

좀 더 빠른 방법을 생각해 봤는데, 두 번의 반복문을 사용한 $O(2n)$의 풀이 방법을 생각했다.

첫 번째 반복문으로 들어있는 정수를 배열에 체크하는 식으로 저장하고,

두 번째 반복문으로 더해서 target이 되는 정수가 있는지 확인하는 식으로 생각했다.

 

근데 문제는 input으로 들어오는 정수의 범위가 $-10^9 ~ 10^9$이기 때문에 최소 20억 개의 배열을 생성해야 하는데,

스택 메모리의 용량이 걸렸다.

 

그래서 다시 생각해 낸 게, 해시를 이용하여 관리하는 방법이다.

해시를 사용하면 해당 아이디어를 이용하면서 n개의 배열만 생성할 수 있고,

find는 $O(1)$ 복잡도를 가지기 때문에, 완전탐색에 비해 속도 면에서 최적화가 가능하다고 생각했다!

 

 

구현

1. 완전 탐색

// Solution 1

vector<int> twoSum(vector<int>& nums, int target) 
{
    vector<int> result;
    int numsSize = nums.size();

    for (int i = 0; i < numsSize; ++i)
    {
        for(int j = i + 1; j< numsSize; ++j)
        {
            if (nums[i] + nums[j] == target)
            {
                result.push_back(i);
                result.push_back(j);
                return result;
            }
        }
    }

    return result;
}

 

2. Hash 활용

// Solution2

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        // @first 단순한 정수 값
        // @second key의 값이 들어있는 index
        unordered_map<int, int> table;

        int numsSize = nums.size();
        vector<int> result;

        for (int i = 0; i < numsSize; ++i)
        {
            int addend = target - nums[i];

            // 더하여 target이 되는 정수가 등록되지 않았을때
            if (table.find(addend) == table.end())
            {
                // 자기자신을 table에 등록
                table[nums[i]] = i;
                continue;
            }

            // 더하여 target이 되는 정수가 등록 되어 있다면, result에 push하여 종료
            result.push_back(i);
            result.push_back(table[addend]);
            break;
        }
        
        return result;
    }
};

 

 

되돌아보기

해시를 이용한 방법에서 처음 코드를 작성할 때, 자기 자신을 table에 등록하는 과정을 첫 번째 순서로 배치하였었는데,

이 때문에 동일 원소를 두 번 사용하게 될 가능성이 있다고 생각했다.

 

해결 방법을 고민 중에, table에서 조회 후 자기 자신을 Table에 등록하게 되면,

모든 원소에 접근을 한 번만 하기 때문에 동일 원소가 사용될 일은 없다고 생각하여 변경하여 풀이했다!

 

3ms가 나왔는데, 서버 환경에 따라 0ms부터 왔다갔다 하나보다

 

 

개선 코드

좀 더 나이스한 return을 할 수 있었다.

// before
result.push_back(i);
result.push_back(table[addend]);
return result;

// after
return {i, table[addend[i]};

 

해당 코드를 이용하여 순서를 바꾸면 좀 더 깔끔해진다!

vector<int> twoSum(vector<int>& nums, int target) 
{
    // @first 단순한 정수 값
    // @second key의 값이 들어있는 index
    unordered_map<int, int> table;

    int numsSize = nums.size();

    for (int i = 0; i < numsSize; ++i)
    {
        int addend = target - nums[i];

        // if부분과  else부분의 처리 순서를 변경 했다.
        if (table.find(addend) != table.end())
        {
        	return {i, table[addend]);
        }
		
        table[nums[i]] = i;
    }

    return {};
}