TIL#27 PYTHON 자료구조(2)

dnpxm387·2020년 8월 8일
0

python

목록 보기
23/43
post-thumbnail

배열을 공부하며 기본적인 예제를 풀었다. 예제 하나에도 여러가지 최적화할 수 있는 방법들이 있다는 것을 다시 한번 알았고 감탄했다. 난 아직도 초보자라는 것을 실감하였다😓

두수의 합

덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라

입력
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
profile
개발자꿈나무🌲

0개의 댓글