문제 링크 : https://leetcode.com/problems/two-sum/
1. Problem
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.
=> 주어진 리스트 nums의 요소들 중 target을 만들 수 있는 조합 출력하기.
단, 요소를 중복으로 사용할 수 없음.
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.2. Solution
2-1. 내 풀이
class Solution(object):
def twoSum(self, nums, target):
for i in range(len(nums)):
for j in range(i):
if nums[i] + nums[j] == target:
return [i, j] 결과:
이중 for문으로 요소별로 더해서 target이 되는 조합일 경우 반환하는 식으로 했는데 풀면서도 이것보다는 더 좋은 해결법이 당연히 있겠지라는 생각이 들음.
-> how? for문 하나만 쓸 순 없을까...
2-2. 다른 풀이 참고해서 재도전
class Solution(object):
def twoSum(self, nums, target):
dic = {}
# i는 0부터 index번호, number는 nums의 리스트 원소
for i, number in enumerate(nums):
key = target-number
# 만약 key가 dic에 있으면 dic[key] 값과, 현재 i를 반환
# key값과 nums[i]를 더하면 target이 되기 때문
if key in dic:
return [dic[key], i]
# key가 dic에 없다면 dic의 {key:value} -> {number:i}로 저장
dic[number] = i결과:
훨씬 좋아졌다. 이 풀이가 자바의 맵 기능을 이용한 것이라고 한다.
ex) nums = [2,7,11,15], target = 9일 때
i = 0, number = 2, dic = {}
key = 9 - 2 = 7
dic이 비어있으므로 추가 dic[number(2)] = 0
i = 1, number = 7, dic = {2:0}
key = 9 - 2 = 2
현재 dic에는 key=2가 있다. 따라서 [dic[key], i] = [dic[2], 1] = [0, 1]을 반환한다.
2-3. 그 외 다르게 도전해보기(추가)
1) 2-1에서 enumerate를 넣어보자.
class Solution(object):
def twoSum(self, nums, target):
for i, a in enumerate(nums): # for i in range(len(nums)):
for j, b in enumerate(nums[:i]): # for j in range(i):
if a + b == target: # if nums[i]+nums[j] == target:
return [i, j]2) 2-2에서 dictionary의 get을 사용해보자.
class Solution(object):
def twoSum(self, nums, target):
dic = {}
for i, number in enumerate(nums):
key = dic.get(target - number) # key = target-number
# key가 None이 아니라면(key가 dict안에 있다는 뜻)
if key is not None: # if key in dic:
return i,j # return [dic[key], i]
dic[number] = i어떻게 이런 발상을 할 수 있는거지???
어떻게 이런 풀이가 바로바로 나올 수 있는거지????
고수의 길은 멀고도 멀다...
