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

문제

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

풀이

생각 회로

1) 조합을 이용한 풀이

리스트의 두 원소를 이용한 합을 구하는 문제이므로, 조합을 구하는 Python의 내장 함수인 combinations()를 활용하면 될 것이라고 생각했다.
하지만, 조합은 리스트의 각 원소가 딱 한 번만 사용되므로, 조합을 이용한 풀이는 example 3: [3,3]의 조건을 만족하지 못한다.
=> 실패

2) HashMap을 이용한 대입

{key : value}를 이용하여 key를 통한 value의 접근을 해야하는데, 단순히 key에는 배열 원소 첨자가 들어와야한다고 생각했다. 하지만, 발상의 전환으로 key 자리에 배열 원소를 넣고, value 자리에 배열 원소 첨자를 넣는 풀이도 가능했다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dict = {}

        for i in range(0, len(nums)):
            dict[nums[i]] = i

        for i in range(0, len(nums)):
            comp = target - nums[i]
            if comp in dict and dict[comp] != i:
                return [i,dict[comp]]

관련 개념

Hashmap

Dictionary 또는 Hash Table이라고도 불린다.
<기본형>

dic = {'name':'pey', 'phone':'0119993323', 'birth': '1118'}

{Key : Value} 형태로 구성되어있으며, Key 값을 통한 Value의 참조가 가능하다.

<예시>

print(grade['name'])
>>> 'pey'

참고

https://wikidocs.net/16
https://velog.io/@taeha7b/datastructure-hashtable
https://velog.io/@sloools/Python-순열Permutation-조합Combination