•
문제 설명 : 제공된 배열 중 일부분을 제외하였을 때, 엄격한 증가를 만들 수 있는 경우가 몇가지인지 확인
•
풀이 방법
◦
푸는 것은 O(N^3) 로 풀 수 있었다.
◦
하지만, O(N^3)는 너무 오래 걸리는 방식(Brute Force)이기 때문에 다른 방법이 없는지 찾아보았다.
•
시간복잡도 :
•
성공 코드
class Solution:
def incremovableSubarrayCount(self, nums: List[int]) -> int:
count = 0
for start in range(len(nums)):
for end in range(start, len(nums)):
target_range = nums[:start] + nums[end + 1:]
if all(target_range[i] < target_range[i + 1] for i in range(len(target_range) - 1)):
count += 1
return count
Python
복사
•
개선 코드(O(N^2))
◦
이 코드의 중요한점은, 엄격한 증가가 유지되는 가장 좌측 배열 및 가장 우측 배열만을 사용하는 점이다.
▪
엄격한 증가가 아닌 부분을 구덩이로 표현하면, 여러 구덩이가 있는 경우 조건을 만족시키기 위해서는 엄격한 증가가 유지되는 좌/우 배열을 남기고 구덩이를 모두 포함하여 없애야하기 때문이다.
•
[1,2,3,4,3,2,5,3,2,6,7,8]
◦
중간에 [5] 만 따로 사용할 수 없다는 의미이다. [1,2,3,4] / [6,7,8] 만 사용 가능하다.
◦
left[i] : nums[0] ~ nums[i] 가 엄격한 증가인지 확인
◦
right[i] : nums[0] ~ nums[i] 가 엄격한 증가인지 확인
◦
별도의 리스트를 슬라이스해서 비교하던 O(N) 방식 대신, left / right 배열을 이용하여 O(1)으로 처리한다.
▪
조건1 : (start == 0 or left[start - 1]) → 좌측 첫 시작 인덱스거나, 엄격한 증가가 유지되는 경우
▪
조건2 : (end == n - 1 or right[end + 1]) → 우측 마지막 인덱스거나, 엄격한 증가가 유지되는 경우
▪
조건3 : (start == 0 or end == n - 1 or nums[start - 1] < nums[end + 1])
•
→ 좌측과 우측을 연결했을 때 엄격한 조합을 경우
•
→ 조건 1/2에 따라 이미 엄격한 조합인 인덱스이지만, 연결이 가능한지 확인
from typing import List
class Solution:
def incremovableSubarrayCount(self, nums: List[int]) -> int:
n = len(nums)
left = [True] * n
right = [True] * n
# Calculate left array
for i in range(1, n):
left[i] = left[i - 1] and nums[i - 1] < nums[i]
# Calculate right array
for i in range(n - 2, -1, -1):
right[i] = right[i + 1] and nums[i] < nums[i + 1]
count = 0
for start in range(n):
for end in range(start, n):
if (start == 0 or left[start - 1]) and (end == n - 1 or right[end + 1]) and (start == 0 or end == n - 1 or nums[start - 1] < nums[end + 1]):
count += 1
return count
Python
복사