(Easy #1) Two Sum

Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

My solution

class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:

        indice = {}

        for i, v in enumerate(nums):

            if v in indice:

                return [indice[v], i]

            else:

                indice[target - v] = i

Runtime: 48s, Memory: 15.1MB

--------------------------------------------------------------------

잡담)

이 문제는 Easy 난이도고 사실상 위와 달리 이중 for문으로 풀어도 된다.

하지만 이직을 할 때, 어떤 회사의 코딩문제에서 이 문제를 접했었다. 알다시피 코딩 테스트는 맞게 푼다고 끝이 아니라 효율적으로 코드를 짜야한다.

처음에는 간단히 2중 for문으로 풀었고 면접관이 자료구조를 이용해서 더 효율적으로 짜보라고 했었는데 자료구조에 대한 개념이 약했던 터라 결국에는 이 문제를 못풀었다.

그래서 면접끝나고 찾아보니 이 문제였고 해시 테이블을 이용해서 푸는 거라고 한다. 파이썬 위주로 코딩했던 터라 해시 테이블이란 네이밍이 생소했지만 알고보니 파이썬은 dictionary로 해시테이블을 default로 제공해주는 것이었다.

참고링크

dictionary는 복잡도 측에서 O(1)을 가지기 때문에 for문보다 훨씬 빠르다는 것이었다..

참고로 그 당시 AI 경력직 코딩테스트였고 5문제중 2문제는 처음에 푼 것처럼 무난히 넘어갔고 3문제는 더 효율적으로 짜보라 했었는데 이 문제만 못짜서 4문제만 제대로 푼 경험이었다. (5문제중 기억나는 문제는 이것말고 edit distance 관련 문제가 있었다.)