[ LeetCode - (06/24) ] - 1. Two Sum(Python)

• 문제링크

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

Two Sum - LeetCode

 

 

 

• 문제

 

 

 

• 시행착오

간단한 문제라 시행착오가 딱히 없었지만, 조건중 하나만 출력하면 된다는 문구를 못봐서 첫시도만에 성공하진 못했다.

 

 

 

• 문제분석

nums : 주어진 숫자의 리스트

target : 목표 숫자값

위 2인자를 받아

nums리스트의 임의의 두 값을 합쳐 target을 만들 수 있는 리스트의 인덱스를 출력하면 된다.

꼭 단 하나의 유효한 값만 출력해야한다.

 

 

 

• 각 파라미터의 유형

nums = [2, 7, 11, 15]

<조건> 

→  2 ≤ nums의 길이 ≤ 10^4

→  -10^9 ≤ nums의 원소 ≤ 10^9

숫자로 이루어진 리스트이며, 위 조건을 충족한다.

 

target

<조건> 

→  -10^9 ≤ target ≤ 10^9

숫자이며, 위 조건을 충족한다.

 

 

 

• 문제접근

※ 작성자가 문제를 보고 든 생각을 차례대로 써본 것이다. 이 순번은 정답이 아니며 매번 다른 생각을 해보길 권장한다.

1) 한 리스트에서 2개를 추출해야하므로 이중반복문이 필요하다 생각했다.

 

 

 

• 최종코드

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]

 

 

 

• Follow-up : 시간복잡도가 O(n^2)보다 덜 소요되게 하는 방법을 생각해보자!

=> 이 부분은 해쉬테이블을 사용하면 된다는 글을 보았지만, 아직 공부하지않아 학습한 후에 쓰도록 하겠다.