[leetcode][42] Trapping Rain Water
문제 : https://leetcode.com/problems/trapping-rain-water/ 땅의 고도를 나타내는 배열이 주어질 때, 비가 내린 후 가둘 수 있는 물의 양을 구해라. 예시로 주어진 [0,1,0,2,1,0,1,3,2,1,2,1] 을 한 번 살펴보자. 예시의 5 인덱스를 보면 가둘 수 있는 물의 양은 양 옆에 있는 고도가 아닌 인덱스 5를 기점으로 왼쪽에 있는 고도 중 가장 높은 것(leftMax)과 오른쪽에 있는 고도 중 가장 높은 것(rightMax)이 관계가 있다. leftMax와 rightMax를 구했다면 이들 중 더 낮은 고도 - 탐색 중인 고도가 가둘 수 있는 물의 양이다. 인덱스 5를 예로 들면 leftMax = 2(index 3). rightMax = 3(index 7)..
2020. 8. 22.
[leetcode][154] Find Minimum in Rotated Sorted Array II
문제 : https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/ 오름차순 정렬된 배열이 있을 때, 어떤 pivot으로 배열이 회전했다고 하자. ex) [0,1,2,3,4,5,6,7] -> [4,5,6,7,0,1,2,3] 회전된 배열이 주어질 때 가장 작은 수를 구하라. 배열안에 수는 중복될 수 있다. 33번 Search in Rotated Sorted Array 와 비슷하게 풀었다. 위 문제와 다른 점은 33번 문제는 회전된 배열에서 특정 수 target을 찾고 배열은 중복된 수가 없다. 왼쪽 오른쪽 배열 오름차순 오름차순 오름차순 (제일 작은수가 왼쪽에 위치) 오름차순 내림차순 제일 작은수가 오른쪽에 위치 내림차순 오름차순 제일 작..
2020. 7. 26.
