[파이썬 알고리즘 인터뷰] 배열 - 빗물 트래핑
·
알고리즘
문제설명 - 높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산하라. 예시 #입력 [0,1,0,2,1,0,1,3,2,1,2,1] #출력 6 풀이 left는 height 배열 왼쪽부터 시작을 하고 right는 배열 오른쪽부터 시작을 한다. left_max 와 right_max는 height 배열의 원소값이다. 둘의 값을 비교하여서 left값이 더 작거나 같을 때는 left 배열값을 1 더해주어 점점 오른쪽으로 이동을하고 반대로 left값이 더 클경우 right 배열값을 1감소시켜 왼쪽으로 이동 시킨다. 비교를 하면서 좌우 기둥 최대높이 Left_max, right_max가 현재높이와의 차이만큼 물높이 volume 을더해나간다. def trap(height): volume = 0 left, ..