LeetCode[ 1 | Python ] Two Sum

문제

https://leetcode.com/problems/two-sum/?envType=study-plan-v2&envId=top-interview-150

정수 배열 nums와 정수 target이 주어지면 nums의 요소 둘을 합해 target 을 만들 수 있는 요소의 주소를 반환해야하는 문제.

풀이

시도

실행 시간 : 33ms
메모리 : 15MB

이전에 비슷한 문제를 투포인터로 풀었지만, 이번엔 해시 테이블로 풀었다.
덕분에 빠른 수행시간을 보장받을 수 있었다.

1. nums를 순회하며 해시테이블에 그 주소를 저장한다.
2. 다시 한번 nums를 순회하며 임의의 수 x와 target - x 가 해시테이블에 존재하는지 찾는다.
   1. 만약 두 수가 같은 수라면 해시테이블에 x가 두 개 이상 존재하는지 판단하고, 존재한다면 주소들을 반환한다.
   2. 같은 수가 아니라면 두 수의 인덱스를 반환한다.

이 코드에서 생각된 문제점은 한 번에 처리 될 수 있는 해시테이블로의 저장과 현재 순회값, 타겟과 현재 순회 값의 차의 존재 여부 판단이었다.

이 둘을 O(n)의 시간복잡도로 해결할 수 있을 것이라고 생각되어 코드를 개선하기로 했다.

class Solution(object):
    def twoSum(self, nums, target):
        dic = {}
        for i in range(len(nums)):
            if not nums[i] in dic:
                dic[nums[i]] = [i]
            else:
                dic[nums[i]].append(i)
        
        for i in range(len(nums)):
            if nums[i] in dic and target - nums[i] in dic:
                if nums[i] == target - nums[i]:
                    if len(dic[nums[i]]) >= 2:
                        return dic[nums[i]]
                else:
                    return [dic[nums[i]][0], dic[target - nums[i]][0]]

개선

실행시간 : 26ms 메모리 :15MB

1. nums를 순회한다.
   1. target - nums[i]가 해시 테이블에 존재한다면 현재 주소와 target - nums[i]의 주소를 반환한다.
   2. 존재하지 않으면 현재 원소의 주소 값을 해시테이블에 저장한다.

현재 원소를 해시테이블에서 바로 찾지 않고 target 값과의 차를 먼저 찾으면 현재 원소는 해시 테이블에 이미 저장되어 있음이 보장됨을 이용해 코드를 작성했다.

결과적으로 모든 수를 저장하지 않고도 해결될 수 있고, 한 번의 반복문으로 해결할 수 있었기 때문에 실행시간과 메모리 사용 모두 줄일 수 있었다.

class Solution(object):
    def twoSum(self, nums, target):
        dic = {}

        for i in range(len(nums)):
            if target - nums[i] in dic:
                return [dic[target - nums[i]], i]
            else:
                dic[nums[i]] = i

생각 & 정리

문제는 6-3, 4-2와 같이 현재 원소와 target - 현재 원소가 같은 경우를 판단하기가 난해 했다.

꽤나 고민을 해보다가, 찾아야하는 수는 두 수이고, O(n)의 시간복잡도를 가지기 때문에 위에서 말한 target - nums[i]가 존재하면 nums[i]가 보장된다는 것을 다시 한번 떠올려 무시해도 되는 조건임을 알아챘다.

문제들을 풀다보면, 무시해도 되는 조건임에도 그 조건을 해결하느라 많은 시간을 보낼 때가 있다. 일반적인 상황에서 세밀한 조건을 다뤄야하는 솔루션은 적절하지 않음에도 그 문제에서 벗어나기가 쉽지 않은 것 같다.