Problem 7. Two Sum
풀이 방법 별 실행 시간 및 Big-O 비교
| 풀이 | 방식 | Big-O | 실행시간 순위 |
|---|---|---|---|
| 1 | 브루트 포스로 계산 | O(n²) | 5위 |
| 2 | in을 이용한 탐색 | O(n²) | 4위 |
| 3 | dictionary로 target - 1st value 조회 | O(n) | 공동 3위 |
| 4 | dictionary로 조회 & for loop 단일화 | O(n) | 공동 3위 |
| 5 | Two Pointer | O(n) | 1위 |
Solution 1. 브루트포스
가능한 모든 경우를 탐색하여 원하는 결과를 얻음
In [2]:
# typing hint를 위한 라이브러리 호출
from typing import List, Set, Dict, Tuple
In [39]:
# 브루트포스 방식, 시간복잡도는 O(n²)
def two_sum_1(nums: list, target: int) -> list:
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
In [41]:
two_sum_1([2,7,11,15], 26)
Out[41]:
Solution 2. in을 이용한 탐색
모든 조합을 비교하기 보다, target에서 첫 번째 값을 뺀 값(target - n)이 존재하는지 탐색
In [37]:
# in의 시간 복잡도는 O(n), 전체 시간 복잡도는 브루트 포스와 동일하게 O(n²)
# 그러나 for문 하나보다 in이 더 가볍고 빠르기 때문에 브루트 포스 방식보다 나음
def two_sum_2(nums: List[int], target: int) -> List[int]:
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)
In [44]:
two_sum_2([2,7,11,15], 26)
Out[44]:
Solution 3. dictionary로 target - 1st value 조회
첫 번째 수를 뺀 결과 키를 조회함
In [24]:
# dictionary는 Hash table로 구현되어 있고, 조회는 평균적으로 O(1), 최악의 경우 O(n)
# 분할 상환 분석에 따라 조회가 O(1)의 시간 복잡도를 가질 때
# 전체 코드의 시간 복잡도는 O(n)
def two_sum_3(nums: List[int], target: int) -> List[int]:
nums_map = {}
# 키와 값을 비꿔서 dictionary로 저장
for i, num in enumerate(nums):
nums_map[num] = i
print(nums_map)
# target에서 첫 번째 수를 뺀 결과를 키로 조회
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]
In [58]:
two_sum_3([2,7,11,15], 26)
Out[58]:
Solution 4. 2차 for loop의 단일화
앞선 dictionary의 for loop문 2개를 하나로 단일화하여 처리
수행 성능 상 큰 차이는 없음
In [45]:
# 전체 코드의 시간 복잡도는 O(n)
def two_sum_4(nums: List[int], target: int) -> List[int]:
nums_map = {}
# nums_map을 모두 생성 후 조회하는 것이 아니라,
# 선 조회 후 없으면 추가로 확장해나가는 방식
for i, num in enumerate(nums):
if target - num in nums_map:
return [nums_map[target - num], i]
nums_map[num] = i
In [56]:
two_sum_4([2,7,11,15], 26)
Out[56]:
Solution 5. Two Pointer
- two pointer의 합이
- target보다 크면 : 오른쪽 포인터를 왼쪽으로 이동해서 sum을 줄임
- target보다 작으면 : 왼쪽 포인터를 오른쪽으로 이동해서 sum을 키움
- 그러나, 입력값이 정렬된 list일 때를 가정한 풀이 방법이므로 정렬 로직이 추가 되어야 함.
In [67]:
# Two Pointer의 시간 복잡도는 O(n)
def two_sum_5(nums: List[int], target: int) -> List[int]:
nums.sort()
left, right = 0, len(nums) - 1
while not left == right:
# 합이 target보다 크면 오른쪽 포인터를 왼쪽으로 이동
if nums[left] + nums[right] > target:
right -= 1
# 합이 target보다 작으면 왼쪽 포인터를 오른쪽으로 이동
elif nums[left] + nums[right] < target:
left += 1
# 합과 target이 동일할 때 정답을 출력
else:
return [left, right]
In [77]:
two_sum_5([2,7,11,15], 26)
Out[77]:
Solution 5에 정렬알고리즘을 추가한 풀이
- index 문제를 해결한 풀이
In [69]:
def two_sum_5_2nd(nums: List[int], target: int) -> List[int]:
# 정렬 결과를 별도로 리턴하여 추가 공간을 사용하는 sorted(list)보다
# list.sort() 제자리 정렬을 선택
sorted_nums = sorted(nums)
left, right = 0, len(nums) - 1
while not left == right:
# 합이 target보다 크면 오른쪽 포인터를 왼쪽으로 이동
if sorted_nums[left] + sorted_nums[right] > target:
right -= 1
# 합이 target보다 작으면 왼쪽 포인터를 오른쪽으로 이동
elif sorted_nums[left] + sorted_nums[right] < target:
left += 1
# 합과 target이 동일할 때 정답을 출력
else:
return [nums.index(sorted_nums[left]), nums.index(sorted_nums[right])]
In [74]:
two_sum_5_2nd([2,7,11,15], 26)
Out[74]:
Problem 8. Trapping Rain Water
풀이 방법 별 실행 시간 및 Big-O 비교
| 풀이 | 방식 | Big-O | 실행시간 순위 |
|---|---|---|---|
| 1 | Two Pointer | O(n) | 1위 |
| 2 | Stack | O(n) | 2위 |
Solution 1. Two Pointer
양쪽에서 출발해 최대 높이를 향해 점점 좁혀오는 Two Pointer 풀이 방법이다.
left_max, right_max는 각각 실시간으로 갱신되는 양 쪽의 최대 높이를 담는 변수이다.
양쪽의 현재 최대 높이(left_max, right_max)와
현재 높이(height[left], height[right])의 차가 곧 담긴 빗물의 양이다.
In [88]:
def trapping_rain_water_1(height: List[int]) -> int:
if len(height) == 0:
return 0
volume = 0
left, right = 0, len(height) - 1
left_max, right_max = height[left], height[right]
while left < right:
# 현재 높이 (height[left], height[right])와
# 기록된 최대 높이(left_max, right_max)를 비교하여 최댓값 갱신
left_max, right_max = max(height[left], left_max),\
max(height[right], right_max)
# 더 높은 곳을 향해 투 포인터 이동
if left_max <= right_max:
volume += left_max - height[left]
left += 1
else:
volume += right_max - height[right]
right -= 1
return volume
In [89]:
trapping_rain_water_1([0,1,0,2,1,0,1,3,2,1,2,1])
Out[89]:
Solution 2. Two Pointer 2
직관적으로 이해하기에 가장 좋은 풀이라고 생각한다.
양쪽에서 출발한 Two Pointer가 담장 + 물을 모두 스캔한다.
이후 왼쪽에서 출발하여 스캔한 결과와 오른쪽에서 출발하여 스캔한 결과를
교집합한 부분을 구하면 담장과 물로 이뤄진 높이를 구할 수 있다.
이 상태에서 담장의 높이들을 빼주면 물이 가진 높이의 합이 산출된다.
In [92]:
def trapping_rain_water_2(height: List[int]) -> int:
n = len(height)
if n == 0:
return 0
left_max = [0] * n
right_max = [0] * n
print(f'Previous results of left_max : {left_max}')
print(f'Previous results of right_max : {right_max}')
left_max[0] = height[0]
right_max[n-1] = height[n-1]
for i in range(1, n):
left_max[i] = max(left_max[i-1], height[i])
for i in range(n-2, -1, -1):
right_max[i] = max(right_max[i+1], height[i])
print(f'Final results of left_max : {left_max}')
print(f'Final results of right_max : {right_max}')
ans = 0
# min(left_max[i], right_max[i])가 의미하는 것 : 물 + 담장 (교집합)
for i in range(n):
ans += min(left_max[i], right_max[i]) - height[i]
return ans
In [93]:
trapping_rain_water_2([0,1,0,2,1,0,1,3,2,1,2,1])
Out[93]:
Solution 3. Stack
현재 높이(height[i])가 이전 높이(height[stack[-1]])보다 높을 때,
꺾이는 변곡점을 기준으로 격차만큼 물의 높이 volume을 채움.
In [3]:
def trapping_rain_water_3(height: List[int]) -> int:
stack = []
volume = 0
for i in range(len(height)):
# 현재 높이가 이전 높이보다 높을 때
while stack and height[i] > height[stack[-1]]:
# 스택에서 꺼내줌
top = stack.pop()
# 스택이 비었다면 append로 넘어감
if not len(stack):
break
# 이전 과의 차이만큼 물 높이 처리
distance = i - stack[-1] - 1
waters = min(height[i], height[stack[-1]]) - height[top]
volume += distance * waters
stack.append(i)
return volume
In [5]:
trapping_rain_water_3([0,1,0,2,1,0,1,3,2,1,2,1])
Out[5]:
출처 : 파이썬알고리즘인터뷰
'Python > Algorithm' 카테고리의 다른 글
| [Python] Linked List (2) (0) | 2021.09.02 |
|---|---|
| [Python] Linked List (1) (0) | 2021.09.01 |
| [Python] Array (2) (0) | 2021.08.31 |
| [Python] 문자열 조작 (0) | 2021.08.23 |
