문제 설명
배열 nums가 주어졌을 때, 모든 요소의 곱이 양수(+)가 되는 부분 배열(subarray) 중에서 가장 긴 길이를 찾아야 합니다.
예를 들어 입력이 nums = [2,-2,-4,5,-3]이라면 정답은 4입니다. 처음 네 개의 요소 [2, -2, -4, 5]로 구성된 부분 배열의 곱은 2 × (-2) × (-4) × 5 = 80으로 양수이기 때문입니다.
핵심 아이디어
곱이 양수가 되려면 부분 배열에 포함된 음수의 개수가 반드시 짝수여야 합니다. 또한 배열에 0이 포함되면 곱이 0이 되어 버리므로, 0을 기준으로 배열을 여러 구간으로 나눈 뒤 각 구간별로 최대 길이를 계산하는 것이 핵심입니다.
알고리즘 단계
- util(s, e) 함수 정의 — 인덱스 s부터 e까지의 구간에서 최대 길이를 계산합니다.
- neg := 0 (구간 내 음수 개수)
- ns := -1, ne := -1 (첫 번째 음수와 마지막 음수의 위치)
- s부터 e까지 순회하면서 nums[i]가 음수이면 neg를 1 증가시키고, 첫 음수라면 ns := i로 저장하며, 매번 ne := i로 갱신합니다.
- neg가 0이거나 짝수라면 전체 구간 길이 (e - s + 1)을 반환합니다.
- neg가 홀수라면 첫 번째 음수를 제외한 경우(e - ns)와 마지막 음수를 제외한 경우(ne - s) 중 더 큰 값을 반환합니다.
- 메인 solve 함수
- ans := 0, s := -1, e := -1로 초기화합니다.
- 배열을 순회하며 0이 아닌 첫 위치를 s로 기록합니다.
- 0을 만나면 직전 인덱스(i-1)까지를 하나의 구간으로 보고 util(s, i-1)을 호출한 후 ans를 갱신하고 s, e를 초기화합니다.
- 순회 종료 후에도 열려 있는 구간(s != -1이고 e == -1)이 있다면 배열 끝까지 처리합니다.
- ans를 반환합니다.
음수가 홀수 개일 때 max(e - ns, ne - s)를 반환하는 이유는, 첫 번째 음수 또는 마지막 음수 중 하나를 구간에서 제외하면 남은 음수 개수가 짝수가 되어 곱이 양수가 되기 때문입니다.
구현 예제
def util(s, e):
neg = 0
ns, ne = -1, -1
for i in range(s, e + 1):
if nums[i] < 0:
neg += 1
if ns == -1:
ns = i
ne = i
if neg == 0 or neg % 2 == 0:
return e - s + 1
else:
return max(e - ns, ne - s)
def solve(nums):
ans = 0
s, e = -1, -1
for i in range(len(nums)):
if nums[i] != 0 and s == -1:
s = i
elif nums[i] == 0 and s != -1:
e = i - 1
ans = max(ans, util(s, e))
s = -1
e = -1
if s != -1 and e == -1:
e = len(nums) - 1
ans = max(ans, util(s, e))
return ans
nums = [2, -2, -4, 5, -3]
print(solve(nums))입력
[2,-2,-4,5,-3]
출력
4
동작 과정 살펴보기
위 예제에서 배열에는 0이 없으므로 전체 배열이 하나의 구간 [0, 4]로 처리됩니다. 이 구간의 음수는 -2, -4, -3으로 총 3개(홀수)이며, 첫 번째 음수 위치 ns = 1, 마지막 음수 위치 ne = 4입니다. 따라서 max(4 - 1, 4 - 0) = max(3, 4) = 4가 반환됩니다.
복잡도 분석
시간 복잡도: O(n) — 각 구간의 util 호출 범위가 서로 겹치지 않으므로 전체 순회 횟수는 배열 길이에 비례합니다.
공간 복잡도: O(1) — 추가적인 자료구조 없이 변수 몇 개만 사용합니다.