9. 선형자료구조 - 배열 (in, 성능 높이기)

 자료구조는 크게 메모리 공간 기반의 연속 방식과 포인터 기반의 연결 방식으로 나뉜다. 배열은 이 중에서 연속 방식의 가장 기본이 되는 자료형이다.

 

https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

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

 

 이 문제는 매우 쉽다. 그러나 최적화할 수 있는 여러가지 방법이 숨어 있어서 코딩 인터뷰 시 높은 빈도로 출제되는 문제라고 한다.

 첫번째 방법은 당연히 모든 배열을 순회하는 부르트포스 방법이다.

 이 방법은 매우 쉬우니 굳이 코드를 올리지 않겠다.

 

 그럼 어떻게 더 빠른 방법을 사용할 수 있을까. 먼저 파이썬의 내장 함수인 in을 사용하는 방법이 있다. target에서 배열 안에 있는 숫자를 뺀후 그 수가 그 뒤로 이어지는 배열 안에 있는지 조회하는 방법이다.

def sol(arr,target):
    for i in range(len(arr)):
        tar=target-arr[i]
        if tar in arr[i+1:]:
            return i,arr[i+1:].index(tar)+i+1

 여기서 in의 시간 복잡도는 O(n)이다. 따라서 전체 시간 복잡도는 이전과 동일한 O(n^2)이다. 그런데 여기서는 같은 시간 복잡도라도 in 연산 쪽이 훨씬 더 가볍고 빠르다. 시간 복잡도는 상수항을 생략하기 때문에 알아차리기 힘들지만 이 풀이의 경우 파이썬의 내부 함수로 구현된 in은 파이썬 레벨에서 매번 값을 비교하는 것에 비해 훨씬 더 빨리 실행된다. 실제로 첫번째 풀이보다 약 6배 이상 빠르다.

 

 여기서 더 시간을 단축할 수 있는 방법이 있다. 위의 두 문제는 이중for문의 형태이므로 단일 for문들로 구성해보면 좋을것 같다는 생각이 든다. 조회를 빨리 하는 방법에는 딕셔너리 자료형이 있기떄문에 이 방법을 사용하면 가능하다. 딕셔너리는 해시 테이블로 구현되어 있고, 이 경우 조회는 평균적으로 O(1)에 가능하다. 

def sol2(nums,target):
    d={}
    for i, num in enumerate(nums):
        d[num] = i
    for i,num in enumerate(nums):
        if target - num in d and i!=d[target-num]:
            return nums.index(num),d[target-num]

 이 방법의 전체 시간 복잡도는 O(n)이 된다. 두번쨰 풀이 방법보다 20배정도 더 빠르다!

 

풀이	방식	실행 시간
1	브루트 포스	5284 밀리초
2	in을 이용한 탐색	964 밀리초
3	딕셔너리 사용	48 밀리초