[CodeKata]Day1

Code Kata 란, 2인 1조의 구성으로 서로 협력하여 하루에 한 문제씩 해결하는 과제입니다.

---

# 문제

two_sum함수에 숫자 리스트와 '특정 수'를 인자로 넘기면, 더해서 '특정 수'가 나오는 index를 배열에 담아 return해 주세요.

• nums: 숫자 배열
• target: 두 수를 더해서 나올 수 있는 합계
• return: 두 수의 index를 가진 숫자 배열

예를 들어,

nums은 [4, 9, 11, 14]
target은 13

nums[0] + nums[1] = 4 + 9 = 13 이죠?

그러면 [0, 1]이 return 되어야 합니다.

+ 가정

target으로 보내는 합계의 조합은 배열 전체 중에 2개 밖에 없다고 가정하겠습니다.

---

# 코드

1. 빈 리스트를 만들어 append로 추가

def two_sum(nums, target):
    # 아래 코드를 작성해주세요.
  new_list = []
  
  for i in nums:	# 길이를 range(len(nums)) 로 지정
    for j in nums:
      if i + j == target:
        new_list.append(nums.index(i))
        new_list.append(nums.index(j))
        return new_list
   return None

2. return 할 때 list 형식으로 반환

def two_sum(nums, target):
    # 아래 코드를 작성해주세요.
  for i in nums:
    for j in nums:
      if i + j == target:
        return [nums.index(i), nums.index(j)]
	return None

3. 중복된 리스트 인덱스끼리는 더하지 않는 조건 추가

def two_sum(nums, target):
    # 아래 코드를 작성해주세요.
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i]+nums[j] == target:
                return [i,j]
    return None

# 풀이 과정

1. 리스트 요소들을 더하기 위해서는 for문 2번을 써야한다.
2. for문에 들어갈 데이터는 리스트 또는 range()다.
   • 리스트로 할 시에는 nums의 인덱스 값을 출력하려면 index()함수를 써야한다.
   • range() 함수를 사용할 때에는 nums의 길이만큼 반복해야하니 len()함수를 써야한다.
3. return 값은 리스트 형태여야 한다.
   • 빈 리스트를 만들어서 append
   • return 할 때 대괄호를 붙이면 리스트 형태가 될까? 시도해본다.
4. 코드 1, 2 도출
5. target 값이 8일때 [0,0] 값 리턴, 리스트 인덱스가 같은 값이 더하는 문제가 있음을 발견
6. 코드 3 도출

# ?

이 문제를 해결할 알고리즘은 어떤 알고리즘이 있을까?

---

+ 그 외 코드

def two_sum(nums, target):
    # 아래 코드를 작성해주세요.
  result=0
  for i in range(len(nums)):
    result=target-nums[i]
    nums2=nums[i+1:]	#나머지 숫자 list를 nums2에 대입

    if result in nums2:
      num1_position = i
      num2_position = nums2.index(result)+i+1
      return [num1_position,num2_position] 
    else:
      continue

def two_sum(nums, target):
	index_map = {}
	for i in range(len(nums)):
		num = nums[i]
		pair = target - num
		if pair in index_map:
			return [index_map[pair], i]
		index_map[num] = i
	return None

+ 참고 자료

배열에서 주어진 합계를 가진 쌍 찾기
시간 복잡도