[python 기초] code-kata week1-1

🖥 Code kata week1 - 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 되어야 합니다.
nums은 [4, 9, 11, 14]
target은 13

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

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

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

풀이

일단, input에 따른 output을 먼저 생각했다.
숫자 list 요소 중, 2개를 골랐을 때 x+y = target이 되어야 한다.
그리고 return은 각 숫자의 index로 구성된 list다.

처음에는 nums에서 순서대로 2개씩 꺼내 합하는 것으로 생각해봤다.

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

그런데 for문은 0,1,2... 이렇게 순서대로 돌아가고 정작 어떤 순서의 숫자가 x와 y가 될지는 알 수 없기 때문에 적합하지 않음.

그래서 더하기 대신 빼기의 방식으로 생각을 바꿨다.
그러면 nums[0]부터 target에서 값을 빼고, 이 값이 다른 숫자들 중에 하나와 일치한다면 x와 y 도출 가능.

그리고 일치하는 숫자를 찾을 때는 nums[0]을 제외하고 찾아야 하므로,
nums[1:]에서 일치하는 숫자를 찾으면 된다.

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

만약 일치하는 숫자가 없다면, 일단 nums[0]은 x나 y가 아닌 것.
위의 코드에서 다시 develop 하면 아래와 같다.

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

작성 후에 이중 for문과 같이 다른 방법에 대해서 얘기해 보다가, 시간복잡도라는 개념에 대해서 배웠다. 자료 유형, 연산에 따라 시간복잡도가 다르다.
이를 활용하면 대략적인 런타임을 가늠할 수 있어 유용할 것 같다.