파이썬 알고리즘 인터뷰_7장.배열

문제. 두수의 합

[2, 7, 11, 15] 가 input으로 들어갔을 때 sum = 9가 되는 두 숫자의 인덱스를 리턴하여라. 

 

풀이 1.  브루트  포스로 계산 

모든 경우의 수를 다 확인하는 방법. 매우 비효율적.

for i in range(len(nums)):
	for j in range(i+1, len(nums)):
    	if nums[i] + num[j] == target:
        	return [i,j]

 

풀이 2.  in을 이용한 탐색

모든 조합을 비교하지 않고 정답, 즉 타겟에서 첫 번째 값을 뺀 값 target - n이 존재하는지 탐색.

for i, n in enumerate(nums):
	complement = target - n
    
    if complement in nums[i+1]:
    	return [nums.index(n), nums[i+1:].index(complement) + (i+1)]

 

풀이 3. 첫번째 수를 뺀 결과 키 조회

키와 값을 바꿔서 딕셔너리로 저장. 

nums_map = {}

for i, num in enumerate(nums):
	nums_map[num] = i
    
    #타겟에서 첫 번째 수를 뺀 결과를 키로 조회
    for i, num in enumerate(nums):
    	if target - num in nums_map and i != nums_map[target-num]:
        	return [i, nums_map[target - num]]

 

풀이 4. 조회 구조 개선 

이중 for 문을 하나로 합쳐서 처리하는 것인데 성능상 큰 이점은 없으므로 패쓰~ 

 

** 풀이 5.  투 포인터 이용 

- 시간 복잡도 : O(n) (효율적 방법)

투 포인터 방법이란? 왼쪽 포인터와 오른쪽 포인터의 합이 타겟보다 크면 오른쪽 포인터를 왼쪽으로, 왼쪽 포인터를 오른쪽으로 옮기면서 값을 조정하는 방법.

시작 : 2, 15

1. 2 + 15 > target(9) 이기 때문에 오른쪽 포인터 -> 왼쪽으로 한칸 움직임.

2. 2 + 11 > target(9) 이기 때문에 오른쪽 포인터 -> 왼쪽으로 한칸 움직임.

3. 2 + 7 = target(9)  종료

*대신 정렬 sort 필요한데 본 문제는 인덱스를 찾는 문제이기 때문에 인덱스가 섞여버림.

left = 0
right = len(nums)-1

while not left == right:
	# 합이 타겟보다 작으면 외쪽 포인터를 오른쪽으로
    if nums[left] + nums[right] < target:
    	left+=1
    # 합이 타겟보다 크면 오른쪽 포인터를 왼쪽으로
    elif nums[left] + nums[right] > target:
    	right-=1
    else:
    	return [left, right]