파이썬 알고리즘 인터뷰 7장: 배열
파이썬 알고리즘 인터뷰 7장: 배열
배열
배열은 값 또는 변수 앨리먼트의 집합으로 구성된 구조로, 하나 이상의 인덱스 또는 키로 식별된다.
-
실제 데이터에서는 전체 크기를 가늠하기 힘들 때가 많다. 때로는 너무 작은 영역을 할당하여 모자라거나, 너무 많은 영역을 할당하여 낭비될 때도 있다
-
이를 위해 미리 크기를 지정하지 않고 자동으로 조정할 수 있는 배열인 동적 배열이 등장했다(파이썬에는 리스트가 바로 동적 배열 자료형이다)
동적배열
미리 초깃값을 작게 잡아 배열을 생성하고, 데이터가 추가 되면서 꽉 채워지면, 늘려주고 모두 복사하는 방식이다.
문제
Q.01 두 수의 합
*문제: https://leetcode.com/problems/two-sum/
from typing import List
nums = [2,7,11,15]
target = 9
저 리스트값 중 두 값을 더하여 타겟값이 반환되는 함수를 작성해야 한다
# 첫 번째 방식(전체 탐색)
def twoSum(nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[i] + nums[j] == target:
return(i,j)
twoSum(nums,target)
(0, 1)
하지만 위 방법은 리스트가 복잡해질 수록 시간복잡도가 올라간다
# 두 번째 방식
# dictionary 방식 활용(LeetCode 해설)
def twoSum(nums: List[int],target: int)-> List[int]:
lst = {}
for i,v in enumerate(nums):
diff = target - v #target값에서 nums의 원소값을 빼면 자연스럽게 두 번째 수를 찾을 수 있습니다.
if diff in lst:
return [lst[diff],i]
if v not in lst:
lst[v] = i # lst에 v값이 없으면 v값을 key로 index 위치를 value로 지정한다
return []
빗물 트래핑
*문제: https://leetcode.com/problems/trapping-rain-water/
#책 해설(투 포인터를 활용한 코드)
def trap(height: List[int])->int:
if not height: #빈리스트 이면 0을 반환하라
return 0
volume = 0
left, right = 0, len(height) - 1 #왼쪽점과 오른쪽 점
left_max, right_max = height[left], height[right] #왼쪽값과 오른쪽 값
while left < right: #왼쪽값이 오른쪽 값보다 작을동안
left_max,right_max = max(height[left],left_max), max(height[right],right_max)
# height[left]와 left_max 중 max 값을 찾아서 left_max에 할당 right_max도 동일한 방식으로 할당
# 더 높은 쪽을 향해 투 포인터 이동
if left_max <= right_max: #left_max가 right_max보다 작거나 같으면
volume += left_max - height[left] #빗방울의 볼륨은 left_max - hieght[left]이 된다
left += 1 #그 후 left에 1을 더한다
else: # 위의 조건이 성립되지 않는다면
volume += right_max - height[right] #빗방울의 볼륨은 right_max - height[right]이 된다
right -= 1#그 후 right에서 1을 뺀ㄷ
# 점점 포인터들이 중앙으로 모이게 된다
return volume
height = [0,1,0,2,1,0,1,3,2,1,2,1]
trap(height)
6