병목현상 제거 하기

1. 병목현상

 

 

 

아래와 같은 서로 다른 정수로 이루어진 배열에서 두 수의 차이가 k 인 원소 쌍의 갯수를 구할 때

 

s = [1, 7, 5, 9, 2, 12, 3]
k = 2
ret = []

 

단순하게 배열의 모든 원소를 훑어가면서 원소 쌍의 차이를 확인할 수도 있지만

 

repeat_count = len(s)

for i in range(repeat_count-1):
    for j in range(i+1, repeat_count):
        if abs(s[i] - s[j]) == 2:
            ret.append((s[i],s[j]))

 

이렇게 코드를 작성한다면 두번째 반복문을 돌면서 같은 원소를 여러번 찾게되어 O(NlogN) 의 시간이 걸리게 된다.

 

 

 

2. 병목현상 제거

 

 

 

dic = {s[i]:i for i in range(len(s))}

confirmed = {}

for i in s:
    
    if i-k in dic and (i-k, i) not in confirmed:
        confirmed[(i, i-k)] = 1
    
    if i+k in dic and (i+k, i) not in confirmed:
        confirmed[(i, i+k)] = 1
        
print(len(confirmed))

 

 

해당 배열을 정렬하거나 그대로 사용하지 않고, 딕셔너리에 담아 key 값으로 인덱싱 할 수 있게 한다면

 

O(N)의 시간안에 문제를 풀 수 있다.

 

 

 

 

Cracking the Coding Interview (Gayle Laakmann McDowell) 의 글로 된 예제를 코드로 작성해 보았습니다.

 

책에 있는 코드가 아니므로 정답이 아닐 수 있습니다.