[Python] LeetCode 문제풀이 :: 1. Two Sum

LeetCode 1번 문제풀이

 

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

Two Sum - LeetCode

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].

풀이 자체는 굉장히 쉬워보이지만 다양한 솔루션을 생각해볼 수 있어서 재밌었던 문제다. 정수가 들어있는 리스트 nums와 정수 target이 주어진다. nums의 요소 중 2가지를 더해 target과 같은 값이 될 때, 두 요소의 인덱스를 리턴하도록 요구한다. 정답이 오직 1개만 나오도록 입력이 주어질 예정이라, 비교적 간단하다.

 

# Solution 1

class Solution:
    def twoSum(self, nums, target):
        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                temp = nums[i] + nums[j]
                if temp == target:
                    return [i, j]

 

우선 이중 반복문으로 아주 간단하게 풀 수 있다.  위에 주어진 예시로 설명하자면, 첫번째 요소인 2에 대해서 다음 요소들인 7, 11, 15를 한번씩 더해보고 합이 9가 되면 각 인덱스를 리턴한다. 기본적인 이중 for문 문제이지만 이렇게 풀 경우 다른 사람들의 풀이에 비해 심각하게 효율이 떨어진다. 나는 실행 시간 약 상위 95프로(=하위 5%), 메모리 약 상위 22프로가 나왔다. 앞으로는 백분율을 단순 백점 만점 점수로 표현해야겠다. 여튼 정답은 맞았지만 더 좋은 풀이가 있는 게 명백해 다른 방법을 생각해보았다.

 

# Solution 2

class Solution:
    def twoSum(self, nums, target):
        vals = []
        for i in range(len(nums)):
            if nums[i] in vals:
                return [vals.index(nums[i]), i]
            vals.append(target - nums[i])

 

이중 반복문을 없애는 게 가장 핵심이라고 생각했다. 리스트를 한 번만 훑으면서 두 개의 요소의 합을 비교할 수 있는 방법. 그러려면 한 번 요소를 탐색했을 때 관련 정보를 임시저장하는 것이 필수라고 생각했다. 그래서 빈 리스트를 만들어줬다. 이 리스트에는 요소 nums[i]와 더하면 target이 나오는 값, 즉 target-nums[i]가 들어갈 것이다. 그리고 매 번 값을 넣어줄 것이므로 vals[i]의 인덱스는 nums[i]의 인덱스와 같다. 만약 nums[i]가 vals[x]와 같다면,  nums[i] +nums[x] = target이 될 것이다.  위의 예시에 따르면, i=0일 때 vals는 비어있으므로 우선 9-2=7을 넣어준다. 현재 vals = [7]이다. 그리고 i=1일 때, nums[1]=7=vals[0]이다. 즉 7과 nums[0]=2를 더하면 target인 9가 된다.

이 방법은 실행 시간 32점, 메모리 80점이 나왔다. 많이 개선됐으나 뭔가 부족하다.

 

# Solution 3

class Solution:
    def twoSum(self, nums, target):
        vals = {}
        for i in range(len(nums)):
            if nums[i] in vals:
                return [vals[nums[i]], i]
            vals[target-nums[i]] = i

 

2번 풀이는 결코 나쁘지 않았다고 생각한다. 그러나 if nums[i] in vals 구문은 사실상 이중 for문이나 다름없다고 생각했다. vals가 리스트였기 때문이다. 그래서 딕셔너리로 바꿔졌다. 키를 통해서 바로 값을 찾을 수 있기 때문이다. 요소 하나를 검사할 때마다 요소 값:인덱스 쌍을 딕셔너리에 추가한다. 예시의 nums를 [2,11,15,7]로 순서만 살짝 바꾼다.

- i=0일 때 vals에는 아무 것도 없다. 그러므로 vals = {"7:0"}이 된다.

- i=1일때 vals에는 11 키가 없다. 그러므로 vals = {"7:0", "-2:1"}이 된다.

- i=2일 때 vals에는 15 키가 없다. vals = {"7:0", "-2:1", "-6:2"}이 된다.

- i=3일 때 vals에는 7키가 있다. 즉 nums[0]과 nums[3]을 더하면 target이 되므로 해당 인덱스를 리턴한다.

이건 런타임 100점, 메모리 42점이 나왔다. 2번 풀이에 비해 메모리가 나빠졌지만, 실행속도가 확실히 개선됐다.

 

이 외에도 동기는 리스트를 정렬하고 양 끝에 각각 포인터 i=0, j=len(num)-1을 잡아줬다. 그리고 nums[i]와 nums[j]를 더해서 target보다 크면 j를 1 깎고, 작으면 i를 키웠다. 그리고 더한 값이 target이 되면 리턴했다. 정렬 덕분에 리스트의 뒤로 갈 수록 값이 커지고 앞으로 갈 수록 값이 작아졌기 때문에 가능했다. 파이썬으로는 안 구현해봤으나, 정렬 시간이 추가로 든다는 단점이 있다고 생각했다. 그리고 정렬 전의 인덱스 값도 저장해야 하므로 메모리에서도 그닥 효율적일 것 같지는 않았다.

 

결론적으로 다양한 풀이가 나와서 재밌는 문제였다.

 

https://github.com/infomuscle/algorithms-leetcode/blob/master/python/1.%20Two%20Sum.py

infomuscle/algorithms-leetcode