자료구조 - 배열 문제 : 두 수의 합

연습문제 : 두 수의 합

숫자들의 배열이 주어지고 표적 숫자가 주어졌다고 하자. 배열에 주어진 숫자들 중 두 개의 숫자를 더하면 표적 숫자가 되는데, 이때 어떤 두 수를 더하면 표적숫자가 되는지 찾는 문제를 풀어봐. 예를 들어서, [2, 8, 19, 37, 4, 5] 가 배열로 주어지고 12 가 표적으로 주어지면 8,4 를 찾아내면 됨.

 

• 입력 배열에는 중복되는 수가 없음.
• 입력 배열에는 합해서 표적이 되는 어떤 두 수가 반드시 있음.
• 출력의 순서는 상관 없음. 위 예시의 경우, 8,4 와 4,8은 둘 다 정답으로 인정.

def twoSum(nums, target):
    for n in nums:
		if (target - n) in nums:
			return n, (target - n)

def main():
    print(twoSum([2, 8, 19, 37, 4, 5], 12)) # (4, 8) 혹은 (8, 4)가 리턴되어야 함.

if __name__ == "__main__":
    main()

>>> 이렇게 하면 for문과 if문에서 배열을 2번 도는 형식이잖아. 그래서 시간이 오려걸려. 더 효율적인 코드로 작성해야돼. 

 

배열을 한번만 돌면서도 결과값을 출력해내기 위해서, sort() 함수를 활용. 배열을 굳이 코드 안에서 도는 게 아니라 내장 함수를 활용해서 배열을 정렬하면, 시간 복잡도가 떨어져. 인자 배열을 오름차순으로 정렬을 해놓으면, 어떤 장점이 있을까? 전에는 nums의 순서가 무작위였기 때문에, 어디에 어떤 숫자가 있는지 짐작이 안되어서 무조건 한 바퀴를 다 돌아야만 했어. 근데, 정렬을 해서 맨 앞의 숫자와 맨 뒤의 숫자의 인덱스를 i, j로 잡아줘.

def twoSum(nums, target):
	nums.sort()
	i = 0
	j = len(nums) - 1

그리고 i가 j보다 작을 동안 계속해서 nums[i]와 nums[j]를 더한 값을 target과 비교해줘.

def twoSum(nums, target):
	nums.sort()
	i = 0
	j = len(nums) - 1
    
    while i < j:
    	sum nums[i] + nums[j]
        if sum == target:
        	return nums[i], nums[j]
        elif sum > target:
        	j -= 1
        else:
        	i += 1

i는 첫번째 원소의 인덱스이고, j는 마지막 원소의 인덱스이기 때문에, sum은 배열에서 맨 첫번째 원소와 마지막 원소를 더한 값이 되는거야. 이때 이 sum이 target이랑 같게 된다면, 우리가 원하는 값을 찾게 된거니까 nums[i]와 nums[j]를 return해주면 돼. 출력 순서는 상관없다고 했으니까, nums[j], nums[i]로 작성해도 상관없음. 

 

그런데, 이렇게 타겟을 바로 만나게 되면 좋겠지만, sum이 target값 보다 좀 더 크다면, target값과 가까워지기 위해서 더 작은 sum을 만들어내야해. 그러기 위해선 nums라는 배열이 이미 오름차순으로 sort가 되어있으니까, 첫 번째 원소가 가장 작고, 마지막 원소가 가장 크잖아. 그래서 target값에 맞춰서 sum값이 작아지기 위해서, 더 앞쪽의 값으로 sum을 구해주는거야. 그래서 j -= 1. 

 

target값이 sum보다 클 수도 있지만, 작을 수도 있잖아. 그래서 target값이 sum보다 작을 때에는 else:로 더 뒤쪽의 sum을 구해주기 위해서 i의 인덱스를 하나씩 늘려. i += 1.

 

그래서 이렇게.

def twoSum(nums, target):
	nums.sort()
	i = 0
	j = len(nums) - 1
	
	while i < j:
		if sum == target:
			return nums[i], nums[j]
		elif sum > target:
			i -= 1
		else:
			j += 1
			
def main():
    print(twoSum([2, 8, 19, 37, 4, 5], 12)) # (4, 8) 혹은 (8, 4)가 리턴되어야 함.

if __name__ == "__main__":
    main()

정리를 해보면, 배열의 맨 첫번째 원소와 맨 뒤의 원소를 더한 값을 기준으로, 인덱스를 옮겨가면서 타겟값에 가까워지게. 그래서 결국 타겟값에 도달할 수 있게 만드는 알고리즘인거야. 똑같은 자료구조의 배열을 쓰더라도 어떻게 코드를 짜느냐에 따라서 이렇게 효율성이 달라질 수 있어.