[Algorithm] #1. 1주차 1번

📌 문제

---

함수에 숫자 리스트와 특정 수를 인자로 넘깁니다.

숫자 리스트 중 2개의 수를 더해서 특정 수가 나오는 index를 배열에 담아 return하는 프로그램을 작성해주세요

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

만약 다음과 같은 숫자리스트를 인자로 받는다면,

num = [4, 9, 11, 14],
target = 13

nums[0] + nums[1] = 4 + 9 = 13이므로

[0, 1] 이 return 됩니다.

✅ 풀이

---

📌 첫번째 풀이

이중 for문을 통한 접근 방식입니다.

첫번째 for문에서 index i의 범위는 0부터 리스트의 길이보다 1을 뺀 만큼까지의 범위를 가집니다.

두번째 for문에서는 자기 자신과 겹치지 않게 하기 위해 두번째 index j의 값을 i+1로 설정했습니다.
시작점은 i의 값보다 1씩 큰 index값이며, 리스트의 길이인 마지막 지점까지 순회합니다.

조건에 충족하는 index값인 i와 j를 리스트의 첫번째와 두번째 값으로 넣어 결과를 반환합니다.

def answer(nums, target):

	for i in range(len(nums)-1):
    	# print(f"i :: {i}")
    	for j in range(i+1, len(nums)) :
      		# print(f"j :: {j}")
      		if (nums[i] + nums[j]) == target :
        		return [i, j]

input = [4, 9, 11, 13]
number = 13
answer(input, number)

디버깅

for문에 대한 이해도나 확신이 안서는 경우 print()를 통해 원하는 index 값으로 순회하고 있는지 확인할 수 있습니다.

📌 또 다른 풀이

짧은 연산이라 이중 for문을 사용했을 때 연산처리속도가 다르다는 것을 체감할 수 없을 것입니다.

하지만 이중 for문을 이용하지 않고 푸는 좋은 방법도 많이 있어 기억과 기록을 해보려고 합니다.

1. result는 dictionary로 다음과 같은 형태를 지닐 것입니다.
   result = {nums[i] : index, ..., nums[len(nums)], len(nums)}

2. subtarct는 target 값에서 nums의 각 요소를 뺀 값입니다.

3. for문을 순회하면서 1번의 dictionary 내부의 key 값 중 subtract 값과 일치하는 값이 있는지 검사합니다.
   있다면 결과의 첫번째 값으로 subtract의 value 값인 리스트 nums의 element를 반환하고, 두번째 값으로 순회를 돌 당시의 index i를 반환합니다.

def answer(nums, target) :
  result = {}
  
  for i in range(len(nums)) :
    key = nums[i]
    subtract = target - key
    
    result[key] = i
    # print(f"""{result}, subtract :: {subtract}, key :: {key}""")
    if subtract in result :
      return [result[subtract], i]
      

print(answer([11,4,13,7,9], 13))