문제

https://leetcode.com/problems/two-sum

리스트와 타겟(int)을 주고, 타겟을 도출하는 리스트 내의 값들의 인덱스를 리턴하는 문제다. 같은 인덱스를 사용할 수 없으며, 하나의 정답만 있다는 전제가 깔려있다.

나는 완전탐색을 사용해서 리스트를 모두 돌렸고, 첫 번째 값은 리스트 전체, 두 번째 값은 첫번재 인덱스+1부터 슬라이싱한 값을 반복문으로 구해서 조건을 만족하는 값이 나오면 리턴하는 방식을 썼다.

나의 정답

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = []
        
        for first in nums:
            first_index = nums.index(first)
            second_nums = nums[first_index+1:] #슬라이싱
            
            for second in second_nums:
            	#만약 인덱스는 다르지만 값은 같은 애들끼리 더해서 타겟이 나왔을 때
                if first + second == target: 
                    result.append(nums.index(first))
                    if first == second:
                        result.append(first_index+second_nums.index(second)+1)
                        return result
                    else:
                        result.append(nums.index(second))
                        return result

결과는 나오게 했는데 brute force 방식이어서 그런지 속도가 너무 느리다 ㅠㅠ (반면 메모리 사용은 상대적으로 적음...?)

Runtime: 3920 ms, faster than 16.74% of Python3 online submissions for Two Sum.
Memory Usage: 14.8 MB, less than 89.63% of Python3 online submissions for Two Sum.

solution을 보니 python을 푼 사람들이 대부분 디셔너리를 만들어 enumerate를 사용해 값을 도출한 것을 보고, 블로그를 써야지 다짐했다.

enumerate

• 반복문 사용 시 몇 번째 반복문인지 확인할 때 사용한다.
• 인덱스 번호와 컬렉션의 원소를 tuple형태로 반환한다. (출처: 링크)

>>> my_list = [1, 2, 3, 4, 5, 5, 5]
>>> for num in enumerate(my_list):
...     print(num)
...
(0, 1)
(1, 2)
(2, 3)
(3, 4)
(4, 5)
(5, 5)
(6, 5)

코드를 돌려보니 속도는 엄청나게 빨라졌지만, 딕셔너리에 결과값을 저장하면서 비교하는 로직이기 때문에 메모리를 많이 차지하게 된다.

위의 내 해답의 경우 리스트에서 같은 값을 가진 요소가 존재할 때 슬라이싱을 해서 반복문을 2중으로 돌리게 된다. 반복문을 두 번 돌리기 때문에 당연히 속도가 느려질 수밖에 없는 반면, 아래 해답에서는 첫 번째 반복문에서 값을 돌리면서 내가 필요한 값을 알게 되기 때문에, 있는지 여부만 따져서 반환하면 된다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = {}
        for index, num in enumerate(nums):
            n = target-num
            if n not in result:
                result[num] = index
            else:
                return [result[n], index]

Runtime: 52 ms, faster than 75.24% of Python3 online submissions for Two Sum.
Memory Usage: 15.2 MB, less than 30.55% of Python3 online submissions for Two Sum.