[leetcode][189] Rotate Array
문제 : leetcode.com/problems/rotate-array/ Follow up에 적힌 공간복잡도 O(1)을 목표로 해보자. 예시로 나온 nums=[1,2,3,4,5,6,7], k=3을 예로 들어보면 일단 nums 배열은 모두 reverse 시킨다. nums=[7,6,5,4,3,2,1] 그리고 앞에서 k개의 원소를 reverse 시키고 nums=[5,6,7,4,3,2,1] k개 이후의 원소들을 다시 reverse 시키면 원하는 배열을 만들 수 있다. nums=[5,6,7,1,2,3,4] 이 때 k는 음수가 아니라는 말만 있고 nums 배열 크기보다 클 수도 있으므로 모듈러 연산해줘야 한다. k = k % |nums| 시간복잡도는 O(N). 공간복잡도는 O(1) 소스코드 : github.com/..
2020. 10. 16.
[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.
