배열

• 메모리 공간 기반의 연속 방식의 기본이 되는 자료형
• 크기는 고정되어 있으며, 변경이 불가능
• 어느 위치에나 O(1)로 조회 가능하다. 메모리가 연속되어 있으므로 시작 주소에서 배열의 위치 * 자료형의 크기를 더해주면 되기 때문이다.

배열의 정적인 크기를 보완하기 위해 나온 동적 배열이 바로 리스트이다 (자바 → ArrayList,

c++→ vector)

문제7. 두수의 합

❓질문

문제 8. 빗물 트래핑

풀이2. 스택 쌓기

def trap(self,height,List[int]) -> int:
	stack =[]
	volumn = 0

	for i in range(len(height)):
		while stack and height[i]<height[stack[-1]]: #stack이 비어있지 않고 현재 높이가 이전 높이 보다 클 때
			top = stack.pop()
			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