LeetCode 1번 Two Sum

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

---

문제 파악

주어진 nums 리스트에서 두 요소를 더해 target의 수와 일치하는 요소들이 있는지 확인하는 문제. 무조건 target이 되는 요소들이 있고 인덱스를 뽑아내면 될 것 같다.

접근 방법

내가 이 문제를 보고 먼저 든 생각은 ‘<완전탐색>을 통해 풀면 어떨까?’이다. 반복문을 통해 풀면 좋겠다고 생각했다. 중복되는 것들을 제외하고 하나씩 다 탐방해서 후보군들에서 답이 되는 인덱스를 뽑아내면 되겠다고 생각했다.

코드 구현

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

배우게 된 점

평소 재귀에 대해서 어렵다고 느껴서 재귀를 잘 사용하지 않고 푸는데 재귀에 대해 다시 강의를 듣고 좀 더 공부해보고 체화해야겠다고 느꼈다.

++ 0703

지금까지는 반복문을 통해 풀었는데 복습을 할 때는 백트래킹을 통해 풀어보자!

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        ans = []
        found = [False]

        def backtracking(start, curr):
            if found[0]:
                return
            if len(curr) == 2:
                if nums[curr[0]] + nums[curr[1]] == target:
                    ans.extend(curr)
                    found[0] = True
                return

            for i in range(start, len(nums)):
                curr.append(i)
                backtracking(i + 1, curr)
                curr.pop()

        backtracking(0, [])
        if ans:
            return ans
        else:
            return -1

풀리긴 하는데 runtime이 매우 길다. 좋은 효율을 보이는 것은 아닌 것 같다. 내 코드 문제일수도 있구... ㅠ