배열을 공부하며 기본적인 예제를 풀었다. 예제 하나에도 여러가지 최적화할 수 있는 방법들이 있다는 것을 다시 한번 알았고 감탄했다. 난 아직도 초보자라는 것을 실감하였다😓
두수의 합
덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라
입력
nums = [2, 7, 11, 15]
target = 9
출력
[0, 1]
⭐️ 브루트 포스 방식
내가 예제를 보고 푼 방식은 한치의 차이도 없이 브루트 포스 방식이었다. 브루트 포스는 가능한 모든 경우에 대해 직접 다 해보는 방식이다. 무차별 대입 방식이라고 한다. 비효율적인 풀이법이라고도 할 수 있다.😭
def target_index(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]차례대로 모두 비교하는 방식을 썼는데 뭔가 스스로 창피해지는 기분이었다. 아직도 갈길이 멀다.😞 이 경우 시간 복잡도는 O(n^2)이다.
⭐️ in을 이용한 탐색
모든 조합을 비교하지 않고 타겟에서 첫번째 값을 뺀 target-n 이 존재하는지 탐색하는 방법이다.
def target_index(nums, target):
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)]처음 코드를 보고는 이해하는데 시간이 좀 걸렸지만 이해하고 나니 이런 방법이 있다는 것도 알게 되었고 조금씩 더 배워나가는 것 같다. 이 경우에는 시간복잡도 자체는 O(n^2)로 브루트포스방식과 같지만 실제 실행속도는 훨씬 빠르다.
⭐️ 딕셔너리를 이용한 방식
타겟에서 첫번째 수를 뺀 수를 바로 조회할 수 있다. 딕셔너리는 해시테이블로 구현되어있고 조회는 평균적으로 O(1)에 가능하다. 위의 두 코드들에 비해서 훨씬 빠른 속도이다.
def target_index(nums, target):
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 [nums.index(num), nums_map[target - num]]위의 소스코드를 하나의 for로 합쳐서 더 간결하게 표현한 방식도 있다. 제일 눈에 잘 들어왔고 정말 감탄했다. 더 열심히 공부해야겠다는 생각이 들었다.
def target_index(nums, target):
nums_map = {}
for i, num in enumerate(nums):
if target - num in nums_map:
return [nums_map[target-num], i]
nums_map[num] = i