목차
정렬된 수 사이에 gap을 채우기
- 문제 링크
- 문제 요약
- 주어진 integer array에서 각 요소를 재배열하거나 작아지게 하는 연산을 통해 각 element 간의 차이가 1 이하가 되도록 만들 때, 마지막 요소의 최대값을 구하라.
- 풀이 요약
- 기존 풀이
- 각 수를 set으로 만들어 정렬한다
- 수 사이의 gap을 찾는다.
- gap이 1 이상인 경우, gap을 채운다.
- 개선 풀이
- 수를 정렬한다.
- 이전 수와 현재 수의 차이가 1 이상인 경우, 현재 수를 이전 수 + 1로 만든다.
- 기존 풀이
def maximumElementAfterDecrementingAndRearranging(arr: List[int]) -> int:
arr sort()
prev = 0
for i in range(1, len(arr)):
if arr[i] - arr[prev] > 1:
arr[i] = arr[prev] + 1
prev = i
return arr[-1]
sum of all odd length subarrays
- 문제 링크
- 문제 요약
- 주어진 integer array에서 odd length subarray의 합을 구하라.
- 기존 풀이
- prefix sum을 구한다.
- 이를 이용해 odd length subarray의 합을 구한다.
- Time complexity: \(O(n^2)\)
- 개선 풀이
- arr[k]가 포함된 subarray의 개수는 \((k+1) * (n-k)\)이다.
- 따라서, arr[k]가 포함된 subarray의 합은 \(arr[k] * (k+1) * (n-k)\)이다.
- 이 중 홀수 길이의 subarray의 갯수는 전체 길이가 홀수인 경우 짝수보다 1개 더 많다.
- Time complexity: \(O(n)\)
def sumOddLengthSubarrays(arr: List[int]) -> int:
n = len(arr)
ans = 0
for i in range(n):
ans += ((i + 1) * (n - i) + 1) // 2 * arr[i]
return ans
2024-04-21